問題描述：Dijkstra算法的驗(yàn)證?

輸入描述：無?

輸出描述：某一頂點(diǎn)到其他各點(diǎn)最短路徑?

用到了graph.h?

*/???

#include???

#include???

#include?"graph.h"??

#define?MaxSize?100??

void?Ppath(int?path[],int?i,int?v)??//前向遞歸查找路徑上的頂點(diǎn)??

{??

int?k;??

k=path[i];??

if?(k==v)??return;??????????//找到了起點(diǎn)則返回??

Ppath(path,k,v);????????????//找頂點(diǎn)k的前一個(gè)頂點(diǎn)??

printf("%d,",k);????????????//輸出頂點(diǎn)k??

}??

void?Dispath(int?dist[],int?path[],int?s[],int?n,int?v)??

{??

int?i;??

for?(i=0;?i

if?(s[i]==1)??

{??

printf("??從%d到%d的最短路徑長度為:%d\t路徑為:",v,i,dist[i]);??

printf("%d,",v);????//輸出路徑上的起點(diǎn)??

Ppath(path,i,v);????//輸出路徑上的中間點(diǎn)??

printf("%d\n",i);???//輸出路徑上的終點(diǎn)??

}??

else??printf("從%d到%d不存在路徑\n",v,i);??

}??

void?Dijkstra(MGraph?g,int?v)??

{??

int?dist[MAXV],path[MAXV];??

int?s[MAXV];??

int?mindis,i,j,u;??

for?(i=0;?i

{??

dist[i]=g.edges[v][i];??????//距離初始化??

s[i]=0;?????????????????????//s[]置空??

if?(g.edges[v][i]//路徑初始化??

path[i]=v;??

else??

path[i]=-1;??

}??

s[v]=1;??

path[v]=0;??????????????//源點(diǎn)編號(hào)v放入s中??

for?(i=0;?i//循環(huán)直到所有頂點(diǎn)的最短路徑都求出??

{??

mindis=INF;?????????????????//mindis置最小長度初值??

for?(j=0;?j//選取不在s中且具有最小距離的頂點(diǎn)u??

if?(s[j]==0?&&?dist[j]

{??

u=j;??

mindis=dist[j];??

}??

s[u]=1;?????????????????????//頂點(diǎn)u加入s中??

for?(j=0;?j//修改不在s中的頂點(diǎn)的距離??

if?(s[j]==0)??

if?(g.edges[u][j]

{??

dist[j]=dist[u]+g.edges[u][j];??

path[j]=u;??

}??

}??

Dispath(dist,path,s,g.n,v);?????//輸出最短路徑??

}??

int?main()??

{??

MGraph?g;??

int?A[7][7]=??

{??

{0,4,6,6,INF,INF,INF},??

{INF,0,1,INF,7,INF,INF},??

{INF,INF,0,INF,6,4,INF},??

{INF,INF,2,0,INF,5,INF},??

{INF,INF,INF,INF,0,INF,6},??

{INF,INF,INF,INF,1,0,8},??

{INF,INF,INF,INF,INF,INF,0}??

};??

ArrayToMat(A[0],?7,?g);??

Dijkstra(g,0);??

return?0;??