迪杰斯拉求最短路徑，會輸出這個最短路徑經過的頂點和最短路徑的長度，求大佬解釋一下這個函式的，為什么這樣寫
這是代碼：
前面定義的東西：
int quanzhi[110][110],vk[110],zuiduan[110];
struct AG //定義結構體存盤景點資訊
{
char mingzi[50];
char xinxi[500];
}q[100]；
迪杰斯拉函式：
void Dijkstra(int v0,int s) //迪杰斯特拉求最短路徑，并輸出路線
{
int min,i,j,u,v;
int p[110],l[110];
memset(p,-1,sizeof(p)); //把p指向的長度為sizeof(p)的空間置-1.(memset位元組進行初始化，sizeof計算存盤位元組數)
memset(l,0,sizeof(l)); //把l指向的長度為sizeof(l)的空間置0.
memset(vk,0,sizeof(vk));//把vk指向的長度為sizeof(vk)的空間置0.
for(i=1;i<=15;i++)
{
zuiduan[i]=quanzhi[v0][i];
if(zuiduan[i]<MAXSIZE) /70能直接到達，即上一站點為v0
p[i]=v0;
}
vk[v0]=1;
for(i=1;i<15;i++)
{
min=MAXSIZE;
for(j=1;j<=15;j++) //每次找出距離v0最近點
{
if(vk[j]==0 && zuiduan[j]<min)
{
min=zuiduan[j];
u=j;
}
}
vk[u]=1; //標記該點
for(v=1;v<=15;v++)
{
if(vk[v]==0 && zuiduan[v]>zuiduan[u]+quanzhi[u][v]) //通過最近點更新其他邊
{
p[v]=u; //存盤更新的邊，即為路線
zuiduan[v]=zuiduan[u]+quanzhi[u][v];
}
}
}
v=s;
i=1;
while(p[v]!=v0) //將路線存入堆疊中，正序輸出
{
l[i++]=p[v];
v=p[v];
}
cout<<endl;
u=i-1;
cout<<"路線:"<<endl;
cout<<q[v0].mingzi<<"--->";//起點
for(i=u;i>=1;i--)
{
cout<<q[l[i]].mingzi<<"--->";
}
cout<<q[s].mingzi<<endl;//終點
cout<<"最短路徑長度為："<<zuiduan[s]<<"米"<<endl;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/269969.html
標籤：C語言
上一篇：java
下一篇：線性表的基本操作的順序表示及實作