#include<stdio.h>
#define INF 32765
void Dijkstra(int cost[][6],int n,int v){
int i,j,u,min,pre;
int dist[6];
int path[6];
int s[6];
for(i=0;i<n;i++){
dist[i]=cost[v][i];
s[i]=0;
if(cost[v][i]<INF)
path[i]=v;
else
path[i]=-1;
}
s[v]=1;
path[v]=0;
for(i=0;i<n;i++){
min=INF;
u=-1;
for(j=0;j<n;j++)
if(s[j]==0&&dist[j]<min){
u=j;
min=dist[j];
}
if(u!=-1){
s[u]=1;
for(j=0;j<n;j++){
if(s[j]==0){
if(cost[u][j]<INF&&cost[u][j]+dist[u]<dist[j]){
dist[j]=cost[u][j]+dist[u];
path[j]=u;
}
}
}
}
}
printf("/nDijkstra 算法：/n");
for(i=0;i<n;i++){
if(i!=v){
printf("%d->%d",v,i);
if(s[i]==1){
printf("路径长为：%2d",dist[i]);
pre=i;
printf("路径逆序为：");
while(pre!=v){
printf("%d,",pre);
pre=path[pre];
}
printf("%d/n",pre);
}
else
printf("不存在路径！/n");
}
}
}
void main(){
int cost[6][6]={
{0,50,10,INF,INF,INF},{INF,0,15,50,10,INF},{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},{INF,INF,INF,30,0,INF},{INF,INF,INF,3,INF,0}
};
Dijkstra(cost,6,1);
printf("/n");
}