数据结构之图（最短路径问题）

求最短路径

问题描述

两种
单源最短路径问题和每队顶点的最短路径问题

对应图有不同的解法

BFS算法

求不带权图最短路径

原来的BFS算法

改进求最短路径的

就是多加d[]数组和path[]数组
d[]数组来记录从顶点到对应节点路径长
path[]数组记录每个对应节点的直接前驱节点
比如3对应的就是6奥
如果是按节点大小顺序入队的话
4前驱节点应该是3
如果不是的话可能是7
看情况
看先处理谁了

Dijkstra算法

BFS算法的局限

不能算带权图最短路径

算法

定义三个数组
第一个数组代表是否找到到其最短路径
第二个数组代表目前为止从初始顶点到对应顶点最短路径的长度
第三个路径上的前驱
第一轮

先遍历跟节点v0进行一个初始的dist[]和path[]的数据更新

数据更新完以后，找对应dist[]最小且final[]不为false的节点Vi，再把final[i]=true
（分析一波：为什么找到dist最小的直接等于true，首先从根节点只有两条路一个v1一个v4这里dist[4]是5比10小，路径长度肯定是相对于v0而言的，所以如果你从别的方式到达v4肯定要经过v1，那就肯定比v1直接到v4大，所以肯定v4的最短路径就出来了，但是v1就不确定，到v1你处理可以从v0直接到v1还可以经过v4（虽然后面不知道）但是是有可能比10小的，所以final[v4]就直接为true）
再通过这个节点遍历其旁边final[]为false的节点进行dist[]和path[]的更新
最后把要所有节点遍历一遍，final[]全是true

dist[]如果找到比原数值小的数
的话
替换对应的dist[]和path[]
注意奥dist和path[]是一起变的，没有说只有一个变

第二轮还是，找遍历dist数组找dist[]最小且final[]不为false的节点Vi，作为下一个节点
且定义这个绩点为true(和前面的分析一样的奥，就是初始顶点变了，不过最后还是从v0到对应顶点的距离)
然后遍历其旁边的边（节点）更新dist和path数组
第三四五轮一样

算法完成后的数组

代码实现

负权值失效

Floyd算法

各点间的最短路径问题！
原理

直接举例吧
第一遍不允许有中转顶点的情况

就由最后一个推出来的矩阵就能确定
某点到某点的最短路径喽
通过path来判断路径
对应的0 1 2代表v0 v1 v2做中转点

代码实现

练习

总结