算法 test2 Dijkstra算法求最短路径_第2关:基于dijsktra算法的最短路径求解

作者：Gausst松鼠会 | 2024-06-13 05:35:48

踩

第2关:基于dijsktra算法的最短路径求解

问题

对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。
在这里插入图片描述

解析

指定起点a存入G中，初始状态下G中只有a,在剩余的数据中找到路径最短的顶点，存入G，再更新剩余数据。重复上述操作，直至完成。

设计

void 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的最短路径 算法7.15
	int v,w,i,j,min;
	Status final[MAX_VERTEX_NUM]; // 辅助矩阵，为真表示该顶点到v0的最短距离已求出，初值为假
	for(v=0;v<G.vexnum;++v)
	{
   
	final[v]=FALSE; // 设初值1
2
3
4
5
6
7
8
9
10

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/711107