Question

用C或C++实现求最短路径的Dijkstra算法

已知：点的名称保存在int A[pointnum]中,点间的路径和权值保存在数组
int B[pointnum][pointnum]中，其中两点间无路径用-1表示
求：void Dijkstra(int B[][],int pointnum,int depart,int dest)
其中int depart表示出发点的名称,int dest表示终点名称
输出结果：depart->中间点1->中间点2->dest

Answer 1

/* 用邻接矩阵表示的图的Dijkstra算法的源程序*/

#include<stdio.h>
#define MAXVEX 100

typedef char VexType;

typedef float AdjType;

typedef struct

{ VexType vexs[MAXVEX]; /* 顶点信息 */

AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */

int n; /* 图的顶点个数 */

}GraphMatrix;

GraphMatrix graph;

typedef struct {

VexType vertex; /* 顶点信息 */

AdjType length; /* 最短路径长度 */

int prevex; /* 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点 */

}Path;

Path dist[6]; /* n为图中顶点个数*/

#define MAX 1e+8

void init(GraphMatrix* pgraph, Path dist[])

{
int i; dist[0].length=0; dist[0].prevex=0;
dist[0].vertex=pgraph->vexs[0];

pgraph->arcs[0][0]=1; /* 表示顶点v0在集合U中 */

for(i=1; i<pgraph->n; i++) /* 初始化集合V-U中顶点的距离值 */

{ dist[i].length=pgraph->arcs[0][i];

dist[i].vertex=pgraph->vexs[i];

if(dist[i].length!=MAX)

dist[i].prevex=0;

else dist[i].prevex= -1;

}

}

void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvex; AdjType min;
init(&graph,dist); /* 初始化，此时集合U中只有顶点v0*/
for(i=1; i<graph.n; i++)
{ min=MAX; minvex=0;
for(j=1; j<graph.n; j++)
if( (graph.arcs[j][j]==0) && (dist[j].length<min) ) /*在V-U中选出距离值最小顶点*/
{ min=dist[j].length; minvex=j; }
if(minvex==0) break; /* 从v0没有路径可以通往集合V-U中的顶点 */
graph.arcs[minvex][minvex]=1; /* 集合V-U中路径最小的顶点为minvex */
for(j=1; j<graph.n; j++) /* 调整集合V-U中的顶点的最短路径 */
{ if(graph.arcs[j][j]==1) continue;
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
dist[j].prevex=minvex;
}
}
}
}

void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}

int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
}
}
}

void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}

int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
这个稍作改动就可以了。

Answer 2

这是我用pascal写的，你转成c语言就行了，很简单，基本是差不多的。

program ex;
var
gh:array[1..100,1..100]of integer;
visit:array[1..100]of boolean;
best:array[1..100]of integer;
min,now,n,e,i,j,k,st:integer;
begin
for i:=1 to 100 do
for j:=1 to 100 do gh[i,j]:=maxint;
fillchar(visit,sizeof(visit),false);
for i:=1 to 100 do best[i]:=maxint;
readln(n);
readln(e);
for i:=1 to e do
begin
readln(i,j,k);
gh[i,j]:=k;
gh[j,i]:=k;
end;
readln(st);
now:=st;
best[now]:=0;
visit[now]:=true;
for i:=1 to n-1 do
begin
for j:=1 to n do
if (gh[now,j]<>maxint) and (best[now]+gh[now,j]<best[j]) then best[j]:=best[now]+gh[now,j];
min:=maxint;
for k:=1 to n do
if (best[k]<min) and (visit[k]=false) then begin min:=best[k]; now:=k; end;
if min=maxint then break;
visit[now]:=true;
end;
for i:=1 to n do write(best[i]);
writeln;
end.

Answer 3

《数据结构》书上有讲的啊

Answer 4

这个确实很简单, 自己做, 边看边学习.

Answer 5

这个很简单…