【大话数据结构C语言】47 最短路径（迪杰斯特拉算法）
【摘要】
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取资源 程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
在网图和非网图中，最短路径的含义是不同的。
网图是两顶点经过的边上
权值之和最少的路径。
非网图是两顶点之间经...
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取资源
程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
在网图和非网图中，最短路径的含义是不同的。
网图是两顶点经过的边上 权值之和最少的路径。
非网图是两顶点之间经过的 边数最少的路径。
我们把路径起始的第一个顶点称为源点，最后一个顶点称为终点。
关于最短路径的算法，常用的有两种：
迪杰斯特拉算法（Dijkstra）
弗洛伊德算法（Floyd）
求V0到V8的最短路径
它并不是一下子就求出了V0到V8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果
dijkstra.c
-
#define MAXVEX 9
-
#define INFINITY 65535
-
-
typedef int Patharc[MAXVEX]; // 用于存储最短路径下标的数组
-
typedef int ShortPathTable[MAXVEX]; // 用于存储到各点最短路径的权值和
-
-
void ShortestPath_Dijkstar(MGraph G, int V0, Patharc *P, ShortPathTable *D)
-
{
-
int v, w, k, min;
-
int final[MAXVEX]; // final[w] = 1 表示已经求得顶点V0到Vw的最短路径
-
-
// 初始化数据
-
for( v=0; v < G.numVertexes; v++ )
-
{
-
final[v] = 0; // 全部顶点初始化为未找到最短路径
-
(*D)[V] = G.arc[V0][v]; // 将与V0点有连线的顶点加上权值
-
(*P)[V] = 0; // 初始化路径数组P为0
-
}
-
(*D)[V0] = 0; // V0至V0的路径为0
-
final[V0] = 1; // V0至V0不需要求路径
-
-
// 开始主循环，每次求得V0到某个V顶点的最短路径
-
for( v=1; v < G.numVertexes; v++ )
-
{
-
min = INFINITY;
-
for( w=0; w < G.numVertexes; w++ )
-
{
-
if( !final[w] && (*D)[w]<min )
-
{
-
k = w;
-
min = (*D)[w];
-
}
-
}
-
final[k] = 1; // 将目前找到的最近的顶点置1
-
-
// 修正当前最短路径及距离
-
for( w=0; w < G.numVextexes; w++ )
-
{
-
// 如果经过v顶点的路径比现在这条路径的长度短的话，更新！
-
if( !final[w] && (min+G.arc[k][w] < (*D)[w]) )
-
{
-
(*D)[w] = min + G.arc[k][w]; // 修改当前路径长度
-
(*p)[w] = k; // 存放前驱顶点
-
}
-
}
-
}
-
}
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/116810789
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）