最短路系列

问题描述

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum fo the weights of its constituent edges is minimized.
The classical problems:
1)The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to tall other vertices in the graph.
2)The single-destination shortest path problem, in which we have to find shortest path frome all vetices in thedirected graph to a single destination vertex v, This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph
3)The all-pairs shortest path problem, in which we have to find shortest path vetween every pair of vetices v, v' in the graph.

相关算法

1) Dijkstra's algorithm solves the single-source shortest path problem.
2) Bellman-Ford algorithm solves the single-source shortest path problem if edge weights may be neaggive.
3)BFS and DFS  sloves for single pair shortest path.
4)Floyed-Warshall algoritym solves all pairs shortest paths

相关算法1(Dijkstra algorithm)

算法步骤如下：

G={V,E}
1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值
　　若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
　　若不存在<V0,Vi>，d(V0, Vi)为∞
2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3. 对其余T中顶点的距离值进行修改：若加进V作中间顶点，从V0到Vi的距离值缩短，则修改此距离值，也就是d(V0,Vi) = min(d(V0, Vi), d(v0, V)+ d(V, Vi))
4.重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

说明：这个其实也是个dp问题，其状态转移方程为：
//d(v)表示当前v到v0(source vertex)的最短路径; w(v1, v2)表示v1到v2的距离，当v1与v2之间没有直接连线时，也就是没有<v1,v2>这条边时，其值为∞
d（v） = min(d(v), d(i)+ w(i, v));

例子：

相关的结果：

图例说明：

源点为A, Dis(i)表示i个点到在当前循环中到源点的最短距离, Min表示每一轮循环中选择的最小距离，Point 表示与当轮选择的Min对应的点；黄色背景表示已经标志的点，绿色背景表示当前循环被选择的，也就是这个点到源点的距离已经是最小的了。(@表示无穷)

选择第二轮进行说明，当前轮遍历了选择了末被标志，且有最小距离的B, 对于与B有相联的点，C，D, E，而C已经被标志，w(i, j)表示边<I, j >之间的边权，根据dis(i) = min(dis(i), Dis(Point) + w(point, i))进行检测是否可以拓展，可以得到，只有E需要被更新，有Dis(E) = Min + w(B, E) = 6 + 7 = 13;


相关代码：

#include<iostream>
using std::cout;
using std::cin;
using std::endl;


#define MAXDIS 999999
int matrix[100][100];
int dis[100];

void Dijkstra(int vertex, int edge, int x) {
    int i, min_pos, j, min_dis;
    bool u[100]; // sign the vertex in the u set while u[i] == true means the vertex i is in the u and have get the shortest_path_weight of x->i;
    // ini the dis;
    for(i = 1; i <= vertex; ++i) {
        dis[i] = matrix[x][i];
        u[i] = false;
    }
    //debug
    for(i = 1; i <= vertex; ++i)
        cout << dis[i] << endl;
    u[x] = true;
    for(j = 2; j <= vertex; ++j)  {// repeat the time;
    // find the min_dis in the dis[],and the min_pos;
        min_dis = MAXDIS;    
        for( i= 1; i <= vertex; ++i)
            if(!u[i] && min_dis > dis[i]) {
                min_dis = dis[i];
                min_pos = i;
            }
        u[min_pos] = true;
        cout << min_pos << endl;
    //update the weight dis[j] = min{dist[j],dist[i]+matrix[i][j]}
        for(i = 1; i <= vertex; ++i) 
            if(!u[i] && matrix[min_pos][i] != MAXDIS)
                if(dis[i] > min_dis + matrix[min_pos][i])
                dis[i] = min_dis + matrix[min_pos][i];
        for(i = 1; i <= vertex; ++i)
                cout << dis[i] << "  ";
        cout << endl;
    }
}

int main() {
    int vertex, edge, i, j, first, second, weight;
    cin >> vertex >> edge;
    // ini the matrx;
    for(i = 1; i <= vertex; ++i)
        for(j = 1; j <= vertex; ++j)
            matrix[i][j] = (i == j ? 0 : MAXDIS);
    for(i = 0; i < edge; ++i) {
        cin >> first >> second >> weight;
        matrix[first][second] = weight;
    }
    cin >> first;
    Dijkstra(vertex, edge, first);v
    for(i = 1; i <= vertex; ++i)
        if(i != first)
        cout << first << " -> " << i << " shortest_path_weight: " <<  dis[i] << endl;
    }

算法补充说明：Disjstra算法不可以处理负权边的情况，主要是因为每一次的循环确定的最小距离就是当前点的最小距离，保证了后面没有情况可以使这个距离更小，这个保证的来源是所有的边都是正数，比如看下面这个反例，如果有V = ｛v1, v2, v3｝,而且E = ｛<v1, v2> = 1, <v1,v3> = 2, <v2, v3> = -2｝,根据算法，以v1为源点，我们第一轮循环要确定dis(v2) = 1是v2到v1的最小路径，但是很明显，因为有了<v2, v3>这个负权边，这个保证并做不到，因为dis(v3) + w(v3, v2) = 0;

相关算法2（Bellman-Ford Algorithm）

算法描述：

这个算法的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。什么是松弛呢？每次松弛操作实际上是对相邻节点的访问，每n次松弛操作保证了所有深度为n的路径的最短长度（只能确定这个，但不能确定哪个点的深度为n,也就是无法确定哪个点已经达到最小路径了），因为一个有V个顶点的没有存在环的图中，其任意两个结点之间的边数最多为V-1，所以松弛操作就做V-1就可以了。直白点说就是用每条边去判断是否可以通过这条边让末点的最短路径变得更小，假设为边<v1, v2>通过的公式为：dis(v2) = min(dis(v2), dis(v1) + w(v1, v2)),这样的操作对于每个点来说最多只有v-1次，因为在不存在负权回路的情况下，两个点的最短路径应该是从起点经过每个点（除了起点与终点）最后到达终点。

算法的主要原理与Dijstra算法一样，也是根据d(v1, v2) = min (d(v1, v2), d(v1, v)+ d(v, v2)); Dijstra算法的基本操作“拓展”是在深度上寻路，这就确定了该算法可以对负边进行操作而不会影响结果，影响主要是表现在Dijstra算法要求每次操作求出来的，也就是将要被标记的点它到源点的距离已经是最短的了，如果存在负权路，就没有办法保证这一点，就会出现结果上的错误，而Bellman-Ford算法则不是，它的基本操作“松弛”是在广度上寻路，也就是说它是到最后过确定了每个点到源点的最短距离，其间的每次操作都让让结果与真实结果更接近。

负权环判定：

Bellman-Ford算法可以用于判断图中是否存在负权环，这主要是因为如果存在负权环的话，则在第V次松弛（得到最短路径只要V-1次）操作中路径仍可以减小。

图例：





图例说明：P表示前一个点是哪个；对第一轮循环说明，对于边<A,B> = -2,判断dis(B)是否可以通过<A,B> 来减小，发现可以，有dis(B) = min(dis(B), dis(A) + w(A, B)); 后面类型，对于边<c, B>再对B判断可否可以进行缩小，发现还还可以，因为此时dis(B) = 7，而dis(C) + w(C, B) = 2,所以令dis(B) = 2, p = C，有该路径从A--->B变为了A--->C--->B，后面一样;这里有一点要说明的是，每一轮循环如，第i轮，只能保证深度为i的路径最小，但不能确定哪个点是深度为i，比如dis(C)，在第一轮中已经确定了最小值，但在第一轮那里并不能知道它已经得到了最小值。


代码（针对有向图）：

#include<iostream>

#define MAXCOST 0x3f3f3f3f
#define N 1010
using std::endl;
using std::cout;
using std::cin;

//store the information of the edge;
struct Edge {
    int start, end;
    int cost;
};

Edge edge[N];
int dis[N];

bool Bellman_Ford(int vertex_num, int edge_num, int original) {
    //init the dis;
    int i, j; 
    for(i = 0; i < vertex_num; ++i)
        dis[i] = (i == original ? 0 : MAXCOST);
    
    //松弛法进行迭代
    for(i = 1; i < vertex_num; ++i) // the time of the loop
        for(j = 1; j <= edge_num; ++j) {
            if(dis[edge[j].end] > dis[edge[j].start] + edge[j].cost)
            dis[edge[j].end] = dis[edge[j].start] + edge[j].cost;
        }

    //determine whether exit the negetive circle or not;
     bool flag = 1;
    for(i = 1; i <= edge_num; ++i)
        if(dis[edge[i].end] > dis[edge[i].start] + edge[i].cost) {
            flag = 0;
            break;
        }
    return flag;
}
int main() {
    int vertex_num, edge_num, original, i;
    cin >> vertex_num >> edge_num;

    for(i = 1; i <= edge_num; ++i) {
        cin >> edge[i].start >> edge[i].end >> edge[i].cost;
    }
    
    cin >> original;

    if(Bellman_Ford(vertex_num, edge_num, original))
        for(i = 0; i < vertex_num; ++i) {
            if(i != original)
                cout << original << " -> " << i << "shortest_path_cost: " << dis[i] << endl;
        }
    else 
        cout << "have negative circle" << endl;    
}

相关算法2（Floyed-Warshall Algorithm）（参考维基）
算法描述：解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，本质上是动态规划，其状态转移方程为：

设 $D_{i,j,k}$ 为从 $i$ 到 $j$ 的只以 $(1..k)$ 集合中的节点为中间節点的最短路径的长度。

若最短路径经过点k，则 $D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$ ；
若最短路径不经过点k，则 $D_{i,j,k}=D_{i,j,k-1}$ 。

因此， $D_{i,j,k}=mbox{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})$ 。

伪码为：

 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 for each vertex v
    dist[v][v] ← 0
 for each edge (u,v)
    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
 for k from 1 to |V|
    for i from 1 to |V|
       for j from 1 to |V|
          if dist[i][j] > dist[i][k] + dist[k][j] 
             dist[i][j] ← dist[i][k] + dist[k][j]
         end if
说明：要记住k,i,j的顺序，不可以反了。

参考网址

http://en.wikipedia.org/wiki/Shortest_path_problem
http://zh.wikipedia.org/zh-cn/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95
http://zh.wikipedia.org/zh/Floyd-Warshall%E7%AE%97%E6%B3%95