How to implement a C / C++ program for Dijkstra's shortest path algorithm.

Question

using adjacency matrix representation of graph?

Answer 1

#include <stdio.h>
#include <stdlib.h>
struct heap{
int vono;
int dis;
};
void makeMinHeap(struct heap[],int,int);
struct heap deleteMinNode(struct heap[]);
void dijkstra(struct heap[],int v);
int noofnode;
int w[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
int d[4];
int location[10];
int visited[10];
int main()
{
    struct heap h[10];
    int i;
    w[0][1]=1;
    w[1][2]=2;
    w[2][3]=3;
    w[1][3]=4;
    w[0][3]=8;
    w[0][2]=5;
    visited[0]=0;
    visited[1]=0;
    visited[2]=0;
    visited[3]=0;
    for(i=0;i<10;i++)
        location[i]=-1;

    dijkstra(h,0);
    for(i=0;i<4;i++)
        printf("%d\n",d[i]);
    return 0;
}
void dijkstra(struct heap h[],int v)
{
    struct heap u;
    int i;
    makeMinHeap(h,0,v);
    visited[v]=1;
    d[v]=0;
    while(isEmptyMinHeap())
    {
    u=deleteMinNode(h);
    for(i=0;i<4;i++)
    {
        if(!visited[i]&&w[u.vono][i])
        {
            d[i]=u.dis+w[u.vono][i];
            makeMinHeap(h,d[i],i);
            visited[i]=1;

        }
        else{
          if(w[u.vono][i]&&u.dis+w[u.vono][i]<d[i])
         {
             d[i]=u.dis+w[u.vono][i];
             h[location[i]].dis=u.dis+w[u.vono][i];
        }
    }
    }
    }
}
int isEmptyMinHeap()
{
    return noofnode;
}
void makeMinHeap(struct heap h[],int dis,int i)
{
    int parent;
    struct heap temp;
    h[i].dis=dis;
    h[i].vono=i;
    location[i]=i;
    while(i!=0)
    {
        parent=(i-1)/2;
        if(h[parent].dis>h[i].dis)
        {
            temp=h[parent];
            h[parent]=h[i];
            h[i]=temp;
            location[h[i].vono]=i;
            location[h[parent].vono]=parent;
        }
        else
            break;

        i=parent;

    }
    noofnode++;
}
struct heap deleteMinNode(struct heap h[])
{
    int i,left;
    struct heap temp;
    struct heap value=h[0];
    h[0]=h[noofnode-1];
    location[h[0].vono]=0;
    noofnode--;
    i=0;
    while(i<noofnode)
    {
        left=2*i+1;

        if(h[left].dis>h[left+1].dis&&left<noofnode-1)
        {
            left++;
        }
        if(h[left].dis<h[i].dis&&left<noofnode)
        {
            temp=h[left];
            h[left]=h[i];
            h[i]=temp;
            location[h[i].vono]=i;
            location[h[left].vono]=left;
           }
        else
        break;
        i=left;
    }
  return value;
}