“最短路径算法:Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。​从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。”

我们解决最短路径问题，常用的是Dijkstra与Floyd算法

Dijkstra（迪杰斯特拉）算法

他的算法思想是按路径长度递增的次序一步一步并入来求取，是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径问题。

算法思想

首先，我们引入一个辅助向量D，它的每个分量D[i]表示当前找到的从起始节点v到终点节点vi的最短路径的长度。它的初始态为：若从节点v到节点vi有弧，则D[i]为弧上的权值，否则D[i]为∞，显然，长度为D[j] = Min{D[i] | vi ∈V}的路径就是从v出发最短的一条路径，路径为(v, vi)。
那么，下一条长度次短的最短路径是哪一条呢？假设次短路径的终点是vk，则可想而知，这条路径或者是(v, vk)或者是(v, vj, vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的权值之和。

一般情况下，假设S为已知求得的最短路径的终点集合，则可证明：一下条最短路径（设其终点为x）或者是弧(v, x)或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S中而长度比此路径短的路径。但是这是不可能的。因为，我们是按路径常度的递增次序来产生个最短路径的，故长度比此路径端的所有路径均已产生，他们的终点必定在S集合中，即假设不成立。

因此下一条次短的最短路径的长度是：D[j] = Min{D[i] | vi ∈ V - S}，其中，D[i]或者是弧(v, vi)的权值，或者是D[k](vk ∈ S)和弧(vk, vi)上权值之和。

算法描述

假设现要求取如下示例图所示的顶点V0与其余各顶点的最短路径：


我们使用Guava的ValueGraph作为该图的数据结构，每个顶点对应一个visited变量来表示节点是在V中还是在S中，初始时S中只有顶点V0。然后从nodes集合中遍历找出从V0出发到各节点路径最短的节点，并将该节点并入S中（即修改该节点的visited属性为true），此时就找到了一个顶点的最短路径。然后，我们看看新加入的顶点是否可以到达其他顶点，并且看看通过该顶点到达其他点的路径长度是否比从V0直接到达更短,如果是，则修改这些顶点的权值(即if (D[j] + arcs[j][k] < D[k]) then D[k] = D[j] + arcs[j][k])。然后又从{V - S}中找最小值，重复上述动作，直到所有顶点都并入S中。

Floyd（弗洛伊德）算法

Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。（动态规划算法是通过拆分问题规模，并定义问题状态与状态的关系，使得问题能够以递推（分治）的方式去解决，最终合并各个拆分的小问题的解为整个问题的解。）

算法思想

从任意节点i到任意节点j的最短路径不外乎2种可能：1)直接从节点i到节点j，2)从节点i经过若干个节点k到节点j。所以，我们假设arcs(i,j)为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立，如果成立，证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短，我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j)，这样一来，当我们遍历完所有节点k，arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。（由于动态规划算法在执行过程中，需要保存大量的临时状态（即小问题的解），因此它天生适用于用矩阵来作为其数据结构，因此在本算法中，我们将不使用Guava-Graph结构，而采用邻接矩阵来作为本例的数据结构）

算法分析及描述

假设现要求取如下示例图所示任意两点之间的最短路径：


我们以一个4x4的邻接矩阵（二维数组arcs[ ][ ]）作为图的数据结构。比如1号节点到2号节点的路径的权值为2，则arcs[1][2] = 2，2号节点无法直接到达4号节点，则arcs[2][4] = ∞(Integer.MAX_VALUE)，则可构造如下矩阵：


有向图的初始邻接矩阵

根据以往的经验，如果要让任意两个顶点（假设从顶点a到顶点b）之间的距离变得更短，唯一的选择就是引入第三个顶点（顶点k），并通过顶点k中转（a -> k ->b）才可能缩短顶点a到顶点b之间的距离。于是，现在的问题便分解为：求取某一个点k，使得经过中转节点k后，使得两点之间的距离可能变短，且还可能需要中转两个或者多个节点才能使两点之间的距离变短。比如图中的4号节点到3号节点（4 -> 3）的距离原本是12（arcs[4][3] = 12），如果在只通过1号节点时中转时（4 -> 1 ->3），距离将缩短为11（arcs[4][1] + arcs[1][3] = 5 + 6 = 11）。其实1号节点到3号节点也可以通过2号节点中转，使得1号到3号节点的路程缩短为5（arcs[1][2] + arcs[2][3] = 2 + 3 = 5），所以如果同时经过1号和2号两个节点中转的话，从4号节点到3号节点的距离会进一步缩短为10。于是，延伸到一般问题：
1、当不经过任意第三节点时，其最短路径为初始路径，即上图中的邻接矩阵所示。
2、当只允许经过1号节点时，求两点之间的最短路径该如何求呢？只需判断arcs[i][1]+arcs[1][j]是否比arcs[i][j]要小即可。arcs[i][j]表示的是从i号顶点到j号顶点之间的距离，arcs[i][1] + arcs[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。循环遍历一遍二维数组，便可以获取在仅仅经过1号节点时的最短距离。

总结

1.Dijkstra算法是计算图中的一个点到其它点的最小路径.
  算法思路: 贪心算法.
    将图中所有点分成 S(已求出解)和U(未求出解)2个点集.dist[i]表示v0到v[i]当前已求得得最短路径.A[n][n]为边集
    1.从剩下的边集合中选出dist最短的边并将边的另一顶点vi从U中加入S.
    2.更新与vi连接的所有且并未在S中的点的dist矩阵值,dist[vk]=min(dist[vk],dist[vi]+A(i,k)).
    3.重复上述操作直到U中无与S中的点相连的点.

2.Floyd算法计算图中任意一对点的最短路径.
  算法思路:  T(n)=O(n^3).
   动态规划法: Dis(i,j) =min(Dis(i,j), Dis(i,k) + Dis(k,j)).

3.Dijkstra算法为啥不能存在负数边?

Dijkstra中S(已求出解)中的每一个点解即最短路径是已求出的,若存在负数路径,可能存在已求出的解不是最优解.

面试题