Dijkstra(single source shortest path)

struct T
{
long x;
long y;
long weight;
};

T a[1000009];

scanf(“%ld %ld %ld %ld”,&node,&edge,&source,&dest);

m=0;
for(i=0;i<edge;i++)
{
scanf(“%ld %ld %ld”,&a[m].x,&a[m].y,&a[m].weight);
m++;
a[m].x=a[m-1].y;   // for bi-directional edge
a[m].y=a[m-1].x;
a[m].weight=a[m-1].weight;
m++;
}

qsort(a,m,sizeof(T),cmp);

for(i=0;i<node;i++)  // initialize
{
start[i]=-1;
dis[i] = inf;
visit[i]=0;
q_dis[i]=-1;
}

for(i=0;i<m;i++)      // connection indexing
if(start[a[i].x]==-1)
start[a[i].x]=i;

dis[   source   ]= 0;
q_x[0] = source;
q_dis[q_x[0]]=0;
n=1;

// maintain a heap, upon the dis[] & for swap, swap both q_x[] & q_dis

for(i=2;i<=node;i++)
{
vertex=-1;
while(1)
{
if(visit[q_x[0]]==0)
{
vertex=q_x[0];
visit[q_x[0]]=1;
}
if(n-1==0)
break;
ReheaP();
if(vertex!=-1)
break;
}

if(vertex==-1)
break;

if(vertex!=dest)
{
if(start[vertex]!=-1)
for(j=start[vertex];j<m;j++)
{
if(a[j].x!=vertex)
break;
if(dis[vertex]+a[j].weight<dis[a[j].y])
{
dis[a[j].y]=dis[vertex]+a[j].weight;
if(visit[a[j].y]==0)
{
if(q_dis[a[j].y]==-1)
{
AddToTheheap(a[i].y); // add node a[i].y to the heap
}
else
UpdateHeap(q_dis[a[j].y]); // update the position of a[j].y node
}

}
}
}
else
break;

if(n==0)
break;

}

if(dis[dest]==inf)
printf(“unreachable\n”);
else
printf(“%ld\n”,dis[dest]);

Advertisements