Dijkstra算法可以解决源点到任意点的最短距离并输出最短路径
准备：
建立一个距离数组d[ n ]，记录每个点到源点的距离是多少
建立一个访问数组v[ n ]，记录每个点是否被访问到
建立一个祖先数组p[ n ]，记录每个节点的父亲节点是什么
选择一个起始点s
执行：
1初始化：所有点到源点的距离都是无穷大
2访问源点，源点到源点的距离自然就变成0，更新与源点相邻的点的距离数组（等于边的权值）
3加入距离最小的点到已访问集合，更新与已访问集合连接的点的距离数组（=min{ 直接距离, 间接距离}）以及更新祖先节点数组p[ n ]
4重复步骤3，直到寻找到终点或者访问完所有节点
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
#define INF 999
int graph[max][max];
int vertex_num;
int edge_num;
int d[max];
int v[max];
int p[max]; Dijkstra(int s){
int i,j,k;
//init part
for(i=;i<vertex_num;i++){
if(graph[s][i]!=){ //if vertex i next to source vertex s
d[i]=graph[s][i];//update the distance array
p[i]=s;
v[i]=;
}else{
d[i]=INF;
p[i]=-;
v[i]=;
} }
d[s]=;
p[s]=;
v[s]=; for(i=;i<vertex_num;i++){
int min=INF;
int u;
for(j=;j<vertex_num;j++){ //find the shortest distance vertex form all the unvisited vertex
if(v[j]==&&d[j]<min){
min=d[j]; //mini distance
u=j; //mini distance vertex u
}
}
v[u]=; //visit u
for(k=;k<vertex_num;k++){
if(v[k]==&&graph[u][k]>&&d[u]+graph[u][k]<d[k]){ //graph[u][k]>0 make sure u and k are connected;
d[k]=d[u]+graph[u][k];
p[k]=u;
}
}
}
printf("Shortest distance form %d:\n",s);
for(i=;i<vertex_num;i++){
printf("%d ",d[i]);
}
printf("\n\n");
}
void show_path(int s,int d){
int cur=d;
int tmp[vertex_num]; int i=;
while(cur!=s){
tmp[i++]=cur;
cur=p[cur];
}
tmp[i]=s;
printf("The shortest path:\n");
while(i>){
printf("%d ->",tmp[i]);
i--;
}
printf("%d",tmp[i]);
}
int main(){
int i,j;
FILE *fin = fopen ("dij.in", "r");
FILE *fout = fopen ("dij.out", "w"); char buf[];
fgets(buf,,fin);
edge_num=atoi(buf); printf("edge_num:%d\n",edge_num);
fgets(buf,,fin);
vertex_num=atoi(buf); printf("vertex_num:%d\n",vertex_num); for(i=;i<edge_num;i++){
int start,end,weight;//start point,end point and the weight of edge
fgets(buf,,fin);
sscanf(buf,"%d %d %d",&start,&end,&weight); printf("start:%d end:%d weight:%d\n",start,end,weight);
graph[start][end]=weight;//init the graph matrix no direct } printf("\n");
printf("Graph matrix:\n");
for(i=;i<vertex_num;i++){
for(j=;j<vertex_num;j++){
printf("%-5d",graph[i][j]);
}
printf("\n");
}
printf("\n");
Dijkstra();
show_path(,);
return ;
}