图论 五 最短路径 最长路径

 

    花几个算法的简易图：

   一、 dijkstra算法：

     

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

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

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

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

 

   二、 warshall算法：

         

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

 算法三个循环for  所有节点

                       for   节点出边

                          for 节点入边

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

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

 

三、开始结束边算法  

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

 

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

 

 

   复杂度上，当然是dijkstra好啦

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