C语言实现最短路问题的算法

＃i nclude<stdio.h>

＃i nclude <stdlib.h>

//Dijkstra算法实现函数

void Dijkstra(int n,int v,int dist[],int prev[],int **cost)

{

int i

int j

int maxint = 65535//定义一个最大的数值，作为不相连的两个节点的代价权值

int *s //定义具有最短路径的节点子集s

s = (int *)malloc(sizeof(int) * n)

//初始化最小路径代价和前一跳节点值

for (i = 1i <= ni++)

{

dist[i] = cost[v][i]

s[i] = 0

if (dist[i] == maxint)

{

prev[i] = 0

}

else

{

prev[i] = v

}

}

dist[v] = 0

s[v] = 1//源节点作为最初的s子集

for (i = 1i <ni++)

{

int temp = maxint

int u = v

//加入具有最小代价的邻居节点到s子集

for (j = 1j <= nj++)

{

if ((!s[j]) &&(dist[j] <temp))

{

u = j

temp = dist[j]

}

}

s[u] = 1

//计算加入新的节点后，更新路径使得其产生代价最短

for (j = 1j <= nj++)

{

if ((!s[j]) &&(cost[u][j] <maxint))

{

int newdist = dist[u] + cost[u][j]

if (newdist <dist[j])

{

dist[j] = newdist

prev[j] = u

}

}

}

}

}

//展示最佳路径函数

void ShowPath(int n,int v,int u,int *dist,int *prev)

{

int j = 0

int w = u

int count = 0

int *way

way=(int *)malloc(sizeof(int)*(n+1))

//回溯路径

while (w != v)

{

count++

way[count] = prev[w]

w = prev[w]

}

//输出路径

printf("the best path is:\n")

for (j = countj >= 1j--)

{

printf("%d ->",way[j])

}

printf("%d\n",u)

}

//主函数，主要做输入输出工作

void main()

{

int i,j,t

int n,v,u

int **cost//代价矩阵

int *dist//最短路径代价

int *prev//前一跳节点空间

printf("please input the node number: ")

scanf("%d",&n)

printf("please input the cost status:\n")

cost=(int **)malloc(sizeof(int)*(n+1))

for (i = 1i <= ni++)

{

cost[i]=(int *)malloc(sizeof(int)*(n+1))

}

//输入代价矩阵

for (j = 1j <= nj++)

{

for (t = 1t <= nt++)

{

scanf("%d",&cost[j][t])

}

}

dist = (int *)malloc(sizeof(int)*n)

prev = (int *)malloc(sizeof(int)*n)

printf("please input the source node: ")

scanf("%d",&v)

//调用dijkstra算法

Dijkstra(n, v, dist, prev, cost)

printf("*****************************\n")

printf("have confirm the best path\n")

printf("*****************************\n")

for(i = 1i <= n i++)

{

if(i!=v)

{

printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i])

printf("the pre-node of node %d is node %d \n",i,prev[i])

ShowPath(n,v,i, dist, prev)

}

}

}

/* 用邻接矩阵表示的图的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 idist[0].length=0dist[0].prevex=0

dist[0].vertex=pgraph->vexs[0]

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

for(i=1i<pgraph->ni++) /* 初始化集合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,minvexAdjType min

init(&graph,dist)/* 初始化，此时集合U中只有顶点v0*/

for(i=1i<graph.ni++)

{ min=MAXminvex=0

for(j=1j<graph.nj++)

if( (graph.arcs[j][j]==0) &&(dist[j].length<min) ) /*在V-U中选出距离值最小顶点*/

{ min=dist[j].lengthminvex=j}

if(minvex==0) break/* 从v0没有路径可以通往集合V-U中的顶点 */

graph.arcs[minvex][minvex]=1/* 集合V-U中路径最小的顶点为minvex */

for(j=1j<graph.nj++) /* 调整集合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=0i<graph.ni++)

for(j=0j<graph.nj++)

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=0i<graph.ni++)

printf("(%.0f %d)",dist[i].length,dist[i].prevex)

return 0

}

}

}

}

void initgraph()

{

int i,j

graph.n=6

for(i=0i<graph.ni++)

for(j=0j<graph.nj++)

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=0i<graph.ni++)

printf("(%.0f %d)",dist[i].length,dist[i].prevex)

return 0

}

这个稍作改动就可以了。

---