目录
1.BFS算法
G纲是个物流离散中心，经常需要往各个城市运东西，怎么运送距离最近——单源最短路径问题
各个城市之间也学要来往，相互之间怎么走距离最近？——每对顶点之间的最短路径
如下图,BFS算法是如何实现最短路径问题的呢？设从顶点2开始，第一次搜索的结点为1号结点和6号结点，路径为1，从1号结点和6号结点开始找相邻的接地，5号结点和3号7号为相邻的结点，然后5号结点周围都是已经访问过的，3号结点和7号结点分别搜索搭配4号和8号结点，路径为4
代码
void BFS_MIN_Distance(Graph G,int u){
//d[i]表示从u到i结点的最短路径
for(int i = 0;i <g.vexnum;i ++){ d[i]="-1" ; 初始化路径长度 path[i]="-1;" 最短路径从哪个顶点过来 } d[u]="0;" visited[u]="TRUE;" enqueue(q,u); while(!isempty(q)) { bfs算法过程 dequeue(q,u); 对头元素u出队 for(w="FirstNeighbor(G,u);" w>=0 ;w = NextNeighbor(G,u,w))
if(!visited[w]){
d[w] = d[u] + 1; // w为u的尚未访问的领结点
path[w] = u; //最短路径应从u到w
visited[w] = u; // 设已访问标记
EnQueue(Q,w); //顶点w入队
}
}
} </g.vexnum;i>
2.Dijkstra算法
BFS算法的局限性
BFS算法只适用于求无权图，或所有边的权值都相同的图。
迪杰斯特拉最短路径算法可以解决
final：标记是否找到最短路径
dist：最短路径长度
path：路径上的前驱
首先遍历所有没确定最短路径的点，v0是0，确定了，在v1,v2,v3,v4中找最短的是v4的5，
然后从经过v4开始 到v1的最短路径变为8，到v2的最短路径变为14，到v3的最短路径值改为7.
同时修改path的值。
第二轮循环中，如果遍历发现最小的v3，把v3final值设为true。然后看其他没有确定的点，经过v3到v2的最短路径为7+6= 13，修改dist[2]的值为13，在修改其path的值。
第四次循环遍历所有结点，发现未遍历的最小的为v2，然后就找不到了 。
通过path【】可知，v0到v2的最短带权路径v2
Original: https://blog.csdn.net/qq_64691289/article/details/128065385
Author: 莫浅子
Title: 详解BFS，Dijkstra算法，Floyd算法是如何解决最短路径问题的
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/805886/
转载文章受原作者版权保护。转载请注明原作者出处！