Open vaakian opened 2 years ago
对无权图(或权值全为1)进行层序遍历, 遍历的层数就是路径长度。遍历的从目标节点层层返回到起始节点,就是最短路径。
属于贪心算法,求解子问题,合并得到答案。,求单源的最短路径。
找到还未确定最短路径,且dist最小的顶点vi,将其final[i]=true。
也就是,本轮结束,可以确定一个较近的最短路径, 将近的最短路径求出,再往下求解,就得到了远的最短路径。
属于动态规划,求各个节点的最短路径。
状态0依赖状态-1, 状态1依赖状态0, 状态2依赖状态0. -1 -> 0 -> 1 -> 2
一、BFS法(无权图)
对无权图(或权值全为1)进行层序遍历, 遍历的层数就是路径长度。遍历的从目标节点层层返回到起始节点,就是最短路径。
二、Dijkstra算法(有权图、无权图)
属于贪心算法,求解子问题,合并得到答案。,求单源的最短路径。
找到还未确定最短路径,且dist最小的顶点vi,将其final[i]=true。
三、Floyd算法((有权图、无权图))
属于动态规划,求各个节点的最短路径。
状态0依赖状态-1, 状态1依赖状态0, 状态2依赖状态0. -1 -> 0 -> 1 -> 2
总结