floyd算法_dijkstra算法代码_第十七题 Dijkstra算法

  本文关键词：dijkstra算法，由笔耕文化传播整理发布。

      或许在生活中，经常会碰到针对某一个问题，在众多的限制条件下，如何去寻找一个最优解？可能大家想到了很多诸如“线性规划”，“动态规划”

这些经典策略，当然有的问题我们可以用贪心来寻求整体最优解，在图论中一个典型的贪心法求最优解的例子就莫过于“最短路径”的问题。

一：概序

   从下图中我要寻找V0到V3的最短路径，你会发现通往他们的两点路径有很多：V0->V4->V3，V0->V1->V3，当然你会认为前者是你要找的最短

路径，那如果说图的顶点非常多，，你还会这么轻易的找到吗？下面我们就要将刚才我们那点贪心的思维系统的整理下。

二：构建

    如果大家已经了解Prim算法，那么dijkstra算法只是在它的上面延伸了下，其实也是很简单的。

1.边节点

  这里有点不一样的地方就是我在边上面定义一个vertexs来记录贪心搜索到某一个节点时曾经走过的节点，比如从V0贪心搜索到V3时，我们V3

的vertexs可能存放着V0,V4,V3这些曾今走过的节点，或许最后这三个节点就是我们要寻找的最短路径。

1 #region 边的信息 2 ///

  本文关键词：dijkstra算法，由笔耕文化传播整理发布。