图论 五 最短路径 最长路径

?

? ? 花几个算法的简易图：

? ?一、 dijkstra算法：

? ? ?

? ? ? ?dijkstra算法需要三个数据结构，a:一个存储已选节点，b：一个存储未选节点，c：一个存储需要不断更新的已经遍历的路径

? ? ? ?算法流程：循环一下算法知道B为空：

? ? ? ?1.选取一个节点为开始节点，遍历开始节点的连通的未访问节点

? ? ? ?2.更新C，取C中总权重最小值的结束节点作为路径下一个循环的开始节点

?

? ?二、 warshall算法：

? ? ? ? ?

? warshall算法：需要邻接矩阵存储图，以便获得出边入边。

?算法三个循环for ?所有节点

? ? ? ? ? ? ? ? ? ? ? ?for ? 节点出边

? ? ? ? ? ? ? ? ? ? ? ? ? for 节点入边

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果出边+入边<两端节点：两端节点=出边+入边

就是将每个节点贡献给自己的入边节点，最后整个图就连在一起啦，可喜可贺，可喜可贺

?

三、开始结束边算法 ?

获得两点之间最大路径，最短路径，可以求出startnode到endnode的所有路径，然后找出来

?

? ? 算法很简单，就是遍历所有节点，然后递归后继，直到递归到看到环了，或是递归到头了，就生成开始节点到结束节点到边拉，可喜可贺，可喜可贺

?

?

? ?复杂度上，当然是dijkstra好啦

? ?在编码上，邻接矩阵比较好用，不用将大的要死的图存在一起，纯属个人见解

?

?

?