Dijkstra单源最短路径的算法：
模板如下：
#include <stdio.h>
#include <string.h>
int nearvex[],lowcost[],table[][];
int path[]; //记录路径，记录直接后继
double dis;
void Dijkstra(int st,int end)
{
int i,j;
int top = -1;
nearvex[st] = -1;
dis = 0;
for(i=1;i<=n;i++)
if( i != st )
{
nearvex[i] = st;
lowcost[i] = table[i][st];
}
for(i=1;i<=n;i++)
{
int min = maxint;
int pmin;
for(j=1;j<=n;j++)
if(nearvex[j] != -1 && lowcost[j] < min)
{
min = lowcost[j];
pmin = j;
}
path[nearvex[pmin]] = pmin;
nearvex[pmin] = -1;
if(pmin == end) return ;
for(j=1;j<=n;j++)
if(nearvex[j] != -1 && lowcost[pmin] + table[j][pmin] < lowcost[j])
{
lowcost[j] = lowcost[pmin] + table[j][pmin];
nearvex[j] = pmin;
}
}
}
//路径的输出
void output(int st , int end)
{
int next = st;
do{
printf("%d ",path[next]);
next = path[next];
}while(next != end);
}
int main()
{
scanf("%d%d",&st,&end);
Dijkstra(st,end);
}
// Single -- Source Shortest Path Problem
