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

来源：百度知道 编辑：UC知道 时间：2024/05/25 10:30:41
已知：点的名称保存在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

/* 用邻接矩阵表示的图的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=p