在交通网络中，常常会提出许多这样的问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。
以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。
最短路径问题的提法很多。在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点S∈V到G中其余各顶点的最短路径。
例如：下图(有向图G14)，假定以v1为源点，则其它各顶点的最短路径如下表所示：
// 定义 状态代码 及 数据类型
#define NULL 0
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFINITY 32767
#define MAX_VERTEX_NUM 20
typedef int Status;
// ---------------------- 图的结构：邻接矩阵 --------------------------//
// 邻接矩阵元素
·typedef struct ArcCell{
int adj; // arc value: >0, INFINITY: no link
char *info;
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
// 图的结构
typedef struct{
char vexs[MAX_VERTEX_NUM][5]; // 顶点数组
AdjMatrix arcs; // 邻接矩阵
int vexnum; // 图当前的顶点数
int arcnum; // 图当前边的个数
}MGraph;
typedef int ShortPathTable[MAX_VERTEX_NUM]; //存放起点到其余每个顶点的最短路径的值
typedef int PathMatrix [MAX_VERTEX_NUM][MAX_VERTEX_NUM];//存放从v0到 v的最短路径上的顶点
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix *P, ShortPathTable *D)
{ /*用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其路径长度D[v]*/
/*若P[v][w]为TRUE，则w是从v0到 v当前求得最短路径上的顶点*/
/*final[v] 为TRUE当且仅当v∈S, ，即已经求得从v0到v的最短路径*/
/*常量INFINITY为边上权值可能的最大值*/
final[MAX_VERTEX_NUM]; //为真表示该顶点到v0的最短距离已求出，初值为假
for(v=0;v
本文档为【Dijkstra算法求最短路径】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483