dijkstra最短路径

来源：百度知道 编辑：UC知道 时间：2024/07/04 02:07:22
void ShortestPath_DIJ(MGraph * G) {
int v,w,i,min,t=0,x,flag=1,v0;
int final[20], D[20], p[20][20];
while(flag) {
printf("请输入一个起始景点编号:");
scanf("%d",&v0);
if(v0<0||v0>G->vexnum){printf("景点编号不存在!请重新输入景点编号:");scanf("%d",&v0);}
if(v0>=0&&v0<G->vexnum) flag=0; }
for(v=0;v<G->vexnum;v++) {
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;w<G->vexnum;w++) p[v][w]=0;
if(D[v]<INFINITY) { p[v][v0]=1;p[v][v]=1; }}
D[v0]=0;final[v0]=1;
for(i=1;i<G->vexnum;i++) {
min=INFINITY;
for(w=0;w<G->vexnum;w++)
if(!final[w])
if(D[w]<min) {v=w;min=D[w];}
final[v]=1;
for(w=0;w<G->vexnum;w++)
if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) {
D[w]=min+G->arcs[v][w].adj;
for(x=0;x<G->vexnum;x++) p[w][x]=p[v][x];
p[w]

大概看了下，程序似乎有些问题，至少有很多做法是不好的。

if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) {
D[w]=min+G->arcs[v][w].adj;
for(x=0;x<G->vexnum;x++) p[w][x]=p[v][x];
p[w][w]=1;}
中，那个for循环应该是无谓的增加复杂度的语句，可能在你的程序里有用，因为我认为你的二维数组P的使用是不合适的，只需要增加一个一维数组path[]，path[i]=j表示结点i的前一个节点是j，只需要把上面那段代码改成：
if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) {
D[w]=min+G->arcs[v][w].adj;
path[w]=v;}

而最后输出路径只需要：
i=t; //t是目标节点
while (i!=V0) //V0是开始节点
{
printf("%d<--",i);
i=path[i];
}
printf("%d\n",V0);