最短路径

描述

所谓最短路径问题是指：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。

Dijkstra算法(迪杰斯特拉算法)

1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
(2) 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

Floyd-Warshall算法

路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

状态转移方程
其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

a)　初始化：D[u,v]=A[u,v]
b)　For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c)　算法结束：D即为所有点对的最短路径矩阵

void floyd(vector<vector<int> > &distmap,//可被更新的邻接矩阵，更新后不能确定原有边
           vector<vector<int> > &path)//路径上到达该点的中转点
//福利：这个函数没有用除INF外的任何全局量，可以直接复制！
{
    const int &NODE=distmap.size();//用邻接矩阵的大小传递顶点个数，减少参数传递
    path.assign(NODE,vector<int>(NODE,-1));//初始化路径数组
    for(int k=1; k!=NODE; ++k)//对于每一个中转点
        for(int i=0; i!=NODE; ++i)//枚举源点
            for(int j=0; j!=NODE; ++j)//枚举终点
                if(distmap[i][j]>distmap[i][k]+distmap[k][j])//不满足三角不等式
                {
                    distmap[i][j]=distmap[i][k]+distmap[k][j];//更新
                    path[i][j]=k;//记录路径
                }
}

AStar算法

估价函数 :F=G+H

Bellman-Ford算法

bool Bellman-Ford(G,w,s)        //图G ，边集 函数 w ，s为源点
  for each vertex v ∈ V(G):     //初始化距离源点距离均为无穷大
    d[v] ←+∞
  d[s] ←0                       //源点距离自身为0
  for i = 1 → |V|:              //松弛操作需要重复多次
    for each edge (u,v) ∈ E(G):
      if d[v] > d[u] + w(u,v):
        d[v] = d[u] + w(u,v)
  for each edge(u,v) ∈ E(G):    //判断是否存在负权环路
    if d[v] > d[u] + w(u,v):
      return false
  return true

SPFA算法(Shortest Path Faster Algorithm)

实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

leeyupeng

最短路径算法