Monday, 3 November 2014

Dijkstra's algorithm C++ code

# define SIZE 8
# define INFINITY 99
#include<iostream>
#include<stdlib.h>
using namespace std;
void build(int n);
void minimum(char key);
void table();
void print();
int n,c,mini,y,m;
int mat[SIZE][SIZE];
char name[SIZE];
struct adjac
{
    char node,k,hv;
    int dv,frend[7];
}ob[SIZE];

int main()
{
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    build(n);
    table();
    system("cls");
    print();
}

void build(int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        cout<<"\nEnter the name of node "<<i+1<<" : ";
        cin>>name[i];
        ob[i].node=name[i];
        ob[i].dv=0;
        ob[i].hv='-';
        ob[i].k='F';
    }

    for(i=0;i<n;i++)
    {
        c=0;
        for(j=0;j<n;j++)
        {
            cout<<"\nEnter weight from node "<<name[i]<<" to node "<<name[j]<<" : ";
            cin>>mat[i][j];
            if(mat[i][j]!=0 && mat[i][j]!=INFINITY)
            {
                ob[i].frend[c++]=j;
            }
        }
         ob[i].frend[c]=-1;
         mat[i][i]=0;
    }
}

void table()
{
    int i,c,j;
    char key;
    cout<<"\nEnter the name of the key node:";
    cin>>key;
    minimum(key);
    for(j=0;j<n-1;j++)
    {
        minimum(ob[mini].node);
    }
}

void minimum(char key)
{
    int i;
     for(i=0;i<n;i++)
    {
        if(ob[i].k=='F')
        {
        if(ob[i].node==key)
        {
            ob[i].k='T';
            c=0;
            while(ob[i].frend[c]!=-1)
            {
                if(ob[ob[i].frend[c]].k=='F')
                {
                ob[ob[i].frend[c]].hv=ob[i].node;
                if(m++==c)
                ob[ob[i].frend[c]].dv+=mat[i][ob[i].frend[c]];
                else
                if(ob[ob[i].frend[c]].dv>ob[i].dv+mat[i][ob[i].frend[c]] || ob[ob[i].frend[c]].dv==0)
                ob[ob[i].frend[c]].dv=ob[i].dv+mat[i][ob[i].frend[c]];
                }
                c++;
            }
            break;
        }
        }
    }
    y=0;
    for(i=0;i<n;i++)
    {
    if(ob[i].dv!=0 && ob[i].k=='F')
    {
        if(y++==0)
        mini=i;
        if(ob[i].dv<ob[mini].dv)
        mini=i;
    }
    }
}

void print()
{
    int i;
    cout<<"\nNode       K            dv           hv\n\n";
    for(i=0;i<n;i++)
    {
        cout<<ob[i].node<<"          "<<ob[i].k<<"            "<<ob[i].dv<<"            "<<ob[i].hv<<endl<<endl;
    }

}

No comments:

Post a Comment