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

如何用C或C++编程实现Dijkstra算法求最短路径问题，不是求最短距离，而是将最短路径给出来~

每次更新节点的最短路的时候，记录是由哪个节点更新过来的，求完最短路后，从终端回溯，直到始点
伪代码一下：
void GetMinDistPath()
{
int dist[nVertex]; //各个点到start_point的距离
int father[nVertex]; //记录是哪个节点更新过来的
int g[nVertex][nVertex]; //邻接矩阵存图，没有边记为infinity
bool vis[nVertex]; //是否已经确定最短路

read_graphy();

init_distance_as_infinity();
init_vis_as_false();

dist[start_point] = 0; vis[start_point] = true;
father[start_point] = -1;

for(int i = 1;i < nVertex;i ++) {
int u = get_not_vis_min_dist_point();
vis[u] = true;
for(int j = 0;j < nVertex;j ++)
if(dist[j] > dist[u] + g[u][j]) {
dist[j] = dist[u] + g[u][j];
father[j] = u; //更新father
}
}

//打印最短路径：start_point <--- end_point
for(int u = end_point;u != -1;u = father[u]) printf("%d ",u);
return;
}

/**************************************************************
* 给定一个带权有向图G = (V，E)，其中每条边的权是一个非负整数。*
* 另外还给定V中的一个顶点，称为源。现在我们要计算从源到所有其 *
* 他各顶点的最短路长度。这里路径长度是路上各边权之和。这个问 *
* 题通常称为单源最短路径问题。 *
***************************************************************/
#include

#define INFINITE 100

void main()
{
int j,i,n,k,t,**w,*s,*p,*d;

cout<<"input the value of n:";
cin>>n;
cout<<endl;

d = new int[n];
s = new int[n];
p = new int[n];
w = new int*[n];

for(i = 0; i < n; i++)
{
w[i] = new int[n];
}

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cin>>w[i][j];


for(s[0] = 1,i = 1; i < n; i++)
{
s[i] = 0;
d[i] = w[0][i];
if(d[i] < INFINITE)
p[i]=0;
else
p[i]=-1;
}



for(i = 1; i < n; i++)
{
t = INFINITE;
k = 1;
for(j = 1; j < n; j++)
if((!s[j]) && (d[j] < t))
{
t = d[j];
k = j;
}
s[k]=1;//point k join the S
for (j = 1; j < n; j++)
if((!s[j]) && (d[j] > d[k] + w[k][j]))
{
d[j] = d[k] + w[k][j];
p[j] = k;
}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
cout<<endl;



}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/

/* 用邻接矩阵表示的图的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;
}
这个稍作改动就可以了。

这是我用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.

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

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

这个很简单…

---

乳源瑶族自治县19391207989： 用C或C++实现求最短路径的Dijkstra算法 - ？
类袁己酮： /* 用邻接矩阵表示的图的Dijkstra算法的源程序*/ #include #define MAXVEX 100 typedef char VexType; typedef float AdjType; typedef struct { VexType vexs[MAXVEX]; /* 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */ int n; /* 图的...

乳源瑶族自治县19391207989： 求!最短路径算法 Dijkstra 用C语言编出来 - ？
类袁己酮： Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪 /*********************************************** 设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异的顶点s称为缘. 单源最短路径问题,或者称为最短路径问题...

乳源瑶族自治县19391207989： 怎么用c语言实现单源最短路径问题?要求是用Dijkstra算法,最好写出所有的代码 ,包括结构定义等等,对一 - ？
类袁己酮： C语言代码://清华大学出版社光盘的代码 void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D) { // 算法7.15// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]// 及其带权长度D[v].// 若P[v][w]为TRUE,则w...

乳源瑶族自治县19391207989： 关于求最短路径的Dijkstra算法的程序源代码 - ？
类袁己酮： 下面是在百度上找到的一篇,已经发到你的邮箱里面了:) Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪 /*********************************************** 设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异...

乳源瑶族自治县19391207989： 跪求最短(长)路径算法,(按要求的)Dijkstra算法C/C++源代码 - ？
类袁己酮： int Locate(MGraph G,VexType v) {for(int i=0;iif(strcmp(v,G.vexs[i])==0) return i; return -1; } void ShortestPath(MGraph G,VexType v,int dist[],int path[]) {//求顶点v到其余各个顶点的最短路径长度,并存放在dist数组中,path数组存放路径 int S[MAX_...

乳源瑶族自治县19391207989： Dijkstra算法的原理和C的编程实现 - ？
类袁己酮： .Dijkstra算法求单源最短路径 语法:result=Dijkstra(Graph G,int n,int s,int t, int path[]);参数:G:图,用邻接矩阵表示n:图的顶点个数s:开始节点t:目标节点path[]:用于返回由开始节点到目标节点的路径返回值:最短路径长度...

乳源瑶族自治县19391207989： 求求dijkstra算法的C实现,要求:有十二个节点,从一点开始依次通过其他的十一个个节点,最后回到初始点,求最短路径的走法! - ？
类袁己酮：[答案] 看看算法导论吧!还有prim算法的!

乳源瑶族自治县19391207989： 急求最短路径算法程序,用C语言或C++？
类袁己酮： 4. 常用算法演示程序 题目:编写常用算法的演示程序 参考:下面算法选择一种实现 矩阵旋转算法 Prim算法 拷贝链表的O(n)算法 随机算法 大数阶乘源码 格雷码算法 算术表达式的计算 寻找链表中间节点算法 模式匹配的KMP算法 最小堆/哈希表/二叉树/平衡二叉树/红黑树 最小生成树 Kruskal算法:(贪心) 最短路径Dijkstra 算法

乳源瑶族自治县19391207989： C++实现D算法F算法求最短路径具体程序 - ？
类袁己酮： #include<stdio.h>#include<iostream>#include<string.h>#include<malloc.h>#include<stdlib.h>#include<string> using namespace std;#define OVERFLOW -2#define OK 1#define ERROR 0#define INFINITY 200//最大值#define MAX_VERTEX_...

乳源瑶族自治县19391207989： 求迪杰斯特拉算法最短路径的算法,有输入与输出算法的C语言编程,谢谢! - ？
类袁己酮： 输入和输出是用邻接矩阵描述的图么,如果是的话我把我的代码COPY给你:#include #include #define INFINITY 9999#define MAX_VERTEX_NUM 20 typedef struct{ int vexs[MAX_VERTEX_NUM]; int arcs[20][20]; int vexnum,arcnum; }MGraph; ...