蘑菇先生学习记

最短路径算法总结

发表于 | 分类于 | 阅读量

　　对最短路径算法进行归纳，包括单源最短路径：Dijkstra、Bellman Ford；所有结点对最短路径Johnson、Floyd Warshall。

图结构存储

　　邻接表或邻接矩阵。

邻接表

链表方式的邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// common define
const int MAXV = 100 + 1;
const int INF = 1e5;
struct E {
    int w; //权重
    int v; //该边终点 
    E* next;//下一条边
    E(){}
    E(int w, int v): w(w), v(v), next(NULL){}
};

struct V {
    E* head;
    int u;//编号
    int d; //上界
    int pi;//前驱节点下标
};

struct Graph {
    V adj[MAXV]; //顶点数组 
    int n; //顶点个数
    int m;
    Graph(){}
};

E* createEdge(int w, int v) {
    return new E(w, v); 
}

void link(Graph* G, int u, E* e) {
    //头插入法
    //e->next = G->adj[u].head;
    //G->adj[u].head = e;

    //尾插入法
    E* p = G->adj[u].head;
    if (p == NULL) { G->adj[u].head = e; return; }
    while (p->next) {
        p = p->next;
    }
    p->next = e;
}

void createGraph(Graph* G) {
    int u, v, k, w;
    cin >> G->n >> G->m; 
    for (u = 1; u <= G->n; ++u) {
        G->adj[u].u = u;
        G->adj[u].head = NULL;
    }
    for (k = 1; k <= G->m; ++k) {
        cin >> u >> v >> w; 
        E* e = createEdge(w, v);
        link(G, u, e);
        //无向图 e = createEdge(w, u);link(G, v, e);
    }
}
void printGraphAdjList(Graph *G) {
    for (int u = 1; u <= G->n; ++u) {
        cout << G->adj[u].u;//输出顶点头下标
        E *p = G->adj[u].head;
        while (p) {
            cout << "----->" << p->v;
            p = p->next;
        }
        cout << endl;
    }
}

Vector方式邻接表

　　还有一种不用链表来保存边，使用vector来保存边，平时写算法题时更方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct E {
    int v;
    int w;
    E(int v, int w): v(v), w(w){}
    E(){}
};
struct Graph {
    vector<E> adj[MAXV];
    int n;
    int m;
};
Graph graph;
void createGraph() {
    int u, v, k, w;
    cin >> graph.n >> graph.m;
    for (k = 1; k <= graph.m; ++k) {
        cin >> u >> v >> w;
        graph.adj[u].push_back(E(v, w));
    }
}

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct GraphMatrix {
    int A[MAXV][MAXV];
    int n;
    int m;
};
GraphMatrix graph;
void createGraph() {
    int u, v, k, w;
    cin >> graph.n >> graph.m;
    for (int i = 1; i <= graph.n; ++i){ 
        fill_n(graph.A[i], graph.n+1, INF);//从下标1开始存，记得graph.n+1
        graph.A[i][i] = 0;
    }
    for (k = 1; k <= graph.m; ++k) {
        cin >> u >> v >> w;
        graph.A[u][v] = w;
    }
}

单源最短路径

Dijkstra

　　Dijkstra算法前提是，不存在负权重的边。图存储使用vector方式的邻接表存储。使用Pair数据结构存入Priority Queue，first保存路径上界，second存节点下标。每次从队列取出新的节点u，relax从u出发可达的所有节点v的路径上界,并加入Queue。注意，这个刚加入的节点V可能之前已经加入过Queue中了，记作v’, 相当于此处重复加入到队列中了，但是最短路径上界d的值不一样，后面会先取到后加入的该节点，记作v’’。“if (d[u] < v_m.first) continue;”的作用就是当再取到v’(v’’更先出队)的时候，判断v’’是否已经出队了，如果d[u]<距离上界，说明v’’出队且更新了最小上界，此时要忽略v’。
　　如果支持Decrease Key的队列的话，完全可以一开始就把所有节点插入到优先队列，后面relax的时候，直接Decrease队列里的节点的路径上界Key就可以了，不存在重复插入到队列的问题。
　　时间复杂度取决于优先队列实现的结构。Dijkstra总共操作n次插入，n次Extract_min,m次decrease key（不支持decrease_key的情况下，我们算法实际上是m次插入，m次extract_min）。如果是二叉堆实现的优先队列，一次插入花费O(logn), 一次Extract_min花费O(logn),一次decrease_key花费O(logn)，总共O(nlogn+nlogn+mlogn)，即O(nlogn+mlogn)，对于m>n的情况，则为O(mlogn)。如果使用斐波那契堆，O(1)插入，O(logn)Extract_min，O(1)decrease key。则总时间为O(n+nlogn+m),对于m>n，则为O(m+nlogn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef pair<int, int> P; //first存d,second存下标
vector<int> d(MAXV, INF);
vector<int> parent(MAXV, 0);
struct cmp {
    bool operator()(P &p1, P &p2) {
        return p1.first > p2.first;
    }
};
void dijkstra(int s) {
    d[s] = 0;//重要!!
    priority_queue<P, vector<P>, cmp> pq;
    pq.push(P(0, s));
    while (!pq.empty()) {
        P v_m = pq.top(); pq.pop();//总共执行n次
        int u = v_m.second;
        if (d[u] < v_m.first) continue;//d[u]小于上界,说明之前更新过了，重复放入的元素
        for (int i = 0; i < graph.adj[u].size(); ++i) {//总共执行m次
            E e = graph.adj[u][i];
            if (d[e.v] > d[u] + e.w) {
                d[e.v] = d[u] + e.w;
                parent[e.v] = u;
                pq.push(P(d[e.v], e.v));
            }
        }
    }
}

　　Running:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void createGraph() {
    int u, v, k, w;
    cin >> graph.n >> graph.m;

    for (k = 1; k <= graph.m; ++k) {
        cin >> u >> v >> w;
        graph.adj[u].push_back(E(v, w));
    }
}
void print_shortest_path(int s, int v) {
    if (v == s) { cout << s << " "; return; }
    if (parent[v] == 0) { cout << "no path from " << s << " to " << v << endl; }
    print_shortest_path(s, parent[v]);
    cout << v << " ";
}

void print_dijkstra(int s) {
    for (int i = 1; i <= graph.n; ++i) {
        print_shortest_path(s, i);
        cout << ",dist=" << d[i] << endl;
    }
}
int main() {
    createGraph();
    dijkstra(1);
    print_dijkstra(1);
}

Bellman Ford

　　Bellman Ford算法的前提是“不存在从源点S可达的负圈”。该算法可以用于检测是否存在源点可达的负圈。

算法导论中

　　存储结构同Dijkstra一致，采用vector方式的邻接链表。时间复杂度O(VE)。每次relax所有边，即遍历出发点u，然后relex从”u出发”的所有边，共relax |V|-1次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool bellman_ford(int s) {
    d[s] = 0;
    for (int k = 1; k <= graph.n - 1; ++k) {//经过k条边,实际上这样子不是每次只看经过小于等于k条边，时间复杂度O(VE)
        for (int u = 1; u <= graph.n; ++u) { //relax从不同顶点出发的所有边,这里面两个循环共调用|E|次。
            for (int j = 0; j < graph.adj[u].size(); ++j) {
                E e = graph.adj[u][j];//边
                int v = e.v;
                if (d[v] > d[u] + e.w) {
                    d[v] = d[u] + e.w;
                    parent[v] = u;
                }
            }//end for
        }//end for
    }//end for
    //检查有没有从s可达的负圈,遍历所有边
    for (int u = 1; u <= graph.n; ++u) {
        for (int j = 0; j < graph.adj[u].size(); ++j) {
            E e = graph.adj[u][j];//边
            if (d[e.v] > d[u] + e.w) {
                return false;
            }
        }//end for
    }//end for
    return true;
}

算法课上

　　动态规划。opt[v][k],代表经过至多k条边，从源点s到v的最短路径。k从1一直到|V|-1。此种需要考虑“到v”的所有边u，因此用邻接矩阵比较方便。(邻接矩阵第v列)。乍看时间复杂度为O(V^3), 实际上是O(VE)，内部两个循环遍历所有的边，总执行次数是O(E)。
$$\begin{equation} opt[v][k]= min \left\{ \begin{aligned} opt[v][k-1] \\\ min_{(u,v) \in E}\{OPT[u, k-1]+w(u, v)\} \end{aligned} \right. \end{equation}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct GraphMatrix {
    int A[MAXV][MAXV];
    int n;
    int m;
};
GraphMatrix graph_2;
vector<int> parent(MAXV, 0);
int opt[MAXV][MAXV];
//得用邻接矩阵存比较方便，因为需要遍历到v节点的所有u.
bool bellman_ford_2(int s) {
    for (int v = 1; v <= graph_2.n; ++v) {
        opt[v][0] = INF;
    }
    //这个初始化在上面之后，保证opt[s][0] = 0;
    for (int k = 0; k < graph_2.n; ++k) {
        opt[s][k] = 0;//到达s，经过k条边
    }
    for (int k = 1; k <= graph_2.n - 1; ++k) {
        for (int v = 1; v <= graph_2.n; ++v) {
            opt[v][k] = opt[v][k - 1];//先赋值初始化！
            for (int u = 1; u <= graph_2.n; ++u) {//获取v的所有前缀,显然就是领接矩阵的第v列
                int w = graph_2.A[u][v];
                if (opt[u][k - 1] + w < opt[v][k]) {//获取所有前缀到达的最小值
                    opt[v][k] = opt[u][k - 1] + w;
                    parent[v] = u;
                }
            }//end for
        }//end for
    }//end for
     //检查有没有从s可达的负圈
    for (int u = 1; u <= graph_2.n; ++u) {
        for (int v = 1; v <= graph_2.n; ++v) {
            if (opt[v][graph_2.n-1] > opt[u][graph_2.n-1] + graph_2.A[u][v]) {
                return false;
            }
        }//end for
    }//end for
    return true;
}
void print_shortest_path(int s, int v) {
    if (v == s) { cout << s << " "; return; }
    if (parent[v] == 0) { cout << "no path from " << s << " to " << v << endl; return; }
    print_shortest_path(s, parent[v]);
    cout << v << " ";
}
void print_path(int s) {
    for (int v = 1; v <= graph_2.n; ++v) {
        print_shortest_path(s, v);
        cout << ",dist=" << opt[v][graph_2.n-1] << endl;
    }
}

void createGraph_2() {
    int u, v, k, w;
    cin >> graph_2.n >> graph_2.m;
    for (int i = 1; i <= graph_2.n; ++i){ 
        fill_n(graph_2.A[i], graph_2.n+1, INF);
        graph_2.A[i][i] = 0;
    }
    for (k = 1; k <= graph_2.m; ++k) {
        cin >> u >> v >> w;
        graph_2.A[u][v] = w;
    }
}
int main() {
    createGraph_2();
    bool no_negative_circle = bellman_ford_2(1);
    if (no_negative_circle) {
        print_path(1);
    }
    else {
        cout << "have negative circle" << endl;
    }
}

所有节点对最短路径

Johnson

　　基于Bellman Ford算法和Dijkstra。可以证明通过下面方式重新赋予权重能够不改变最短路径。
$$\hat{w}(u,v) = w(u,v)+h(u)-h(v), h函数将节点映射到实数上$$
　　考虑到Bellman Ford允许负权重边存在，不允许负圈存在。而Dijkstra不允许负权重边存在，如果能够通过上面的构造将负权重转成非负的权重。那么就可以使用Dijkstra算法。这样处理完，整体思路是先用Bellman Ford检查是否存在负圈，无负圈的情况下，再针对每个起始点，使用Dijkstra算法找到所有节点对最短路径。
　　具体构造，增加一个源点S’,S’到各个顶点的权重为0，且是单向的。因为单向的，S’的加入不可能导致新圈的产生，另外S’可达任意节点，则新图G’如果存在从S’可达的负圈，则原图一定存在某个负圈。可以运行Bellman Ford算法先检查从S’出发是否存在可达的负圈。
　　对于权重修改，任意顶点u的h映射函数定义为，从S’到u的最短路径长度，即h(u) = dist(S’,u)。这样构造新的权重，\(\hat{w}(u,v) = w(u,v)+dist(S’,u)-dist(S’,v) \geq 0\)，可以保证新权重大于等于0，因为如果小于等于0，则\(dist(S’,v) \geq w(u,v) + dist(S’, u)\),显然这和dist(S’,v)是从S’到v的最短路径矛盾。
因此对于增加完S’的新图，保证了权重为0，可以对每个节点使用Dijkstra算法。实际的距离\(dist(u,v)=\hat{dist}(u,v) - dist(S’,u) + dist(S’, v)\),\(\hat{dist}(u,v)\)为修改完权重后\(u->v\)的最短路径。
　　该算法对稀疏图很有效，即边的数量比较少的情况下。如果Dijkstra使用斐波那契队列实现优先队列，即时间复杂度为\(O(m+nlogn)\),则Johnson算法时间复杂度为\(O(mn+n^2logn)\)，显然对于稠密图m>>n,则m占主导，算法较慢。此时使用下述讨论的Floyd Warshall算法较好，该算法时间复杂度为\(O(V^3)\)，跟m无关，对于稠密图会很有优势。
　　完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

//节点编号1 ~ |V|
const int MAXV = 100 + 1;
const int INF = 1e5;

vector<vector<int>> dist(MAXV, vector<int>(MAXV, INF)); // 距离矩阵，第一维是起始点,0编号存放S'到各个点的距离
vector<vector<int>> parent(MAXV, vector<int>(MAXV, 0));//前驱子图，第一维是起始点

struct E {
    int v;
    int w;
    E(int v, int w) : v(v), w(w) {}
    E() {}
};
typedef pair<int, int> P; //first存d,second存下标

struct Graph {
    vector<E> adj[MAXV];
    int n;
    int m;
};
Graph graph;

bool bellman_ford(int s) {
    dist[s][s] = 0;
    int n = graph.n + 1;
    for (int k = 1; k <= n - 1; ++k) {
        for (int u = 0; u <= graph.n; ++u) { //u从0开始，0代表新添加的点
            for (int j = 0; j < graph.adj[u].size(); ++j) {
                E e = graph.adj[u][j];
                int v = e.v;
                if (dist[s][v] > dist[s][u] + e.w) {
                    dist[s][v] = dist[s][u] + e.w;
                }//end if
            }//end for
        }//end for
    }//end for
     //检查有没有从s可达的负圈
    for (int u = 0; u <= graph.n; ++u) { // u从0开始
        for (int j = 0; j < graph.adj[u].size(); ++j) {
            E e = graph.adj[u][j];//边
            if (dist[s][e.v] > dist[s][u] + e.w) {
                return false;
            }//endif
        }//end for
    }//end for
    return true;
}

struct cmp {
    bool operator()(P &p1, P &p2) {
        return p1.first > p2.first;
    }
};

//O(nlogn + mlogn), m>n时，O(mlogn); 斐波那契堆 O(nlogn + m)
void dijkstra(int s) {
    dist[s][s] = 0;
    priority_queue<P, vector<P>, cmp> pq;
    pq.push(P(0, s));
    while (!pq.empty()) {
        P v_m = pq.top(); pq.pop();//共执行n次,logn 
        int u = v_m.second;
        if (dist[s][u] < v_m.first) continue;//d[u]小于上界,说明之前更新过了，重复放入的元素
        for (int i = 0; i < graph.adj[u].size(); ++i) {//共执行m次
            E e = graph.adj[u][i];
            if (dist[s][e.v] > dist[s][u] + e.w) {
                dist[s][e.v] = dist[s][u] + e.w;
                parent[s][e.v] = u;
                pq.push(P(dist[s][e.v], e.v));//logn
            }
        }
    }
}

//O(mnlogn+n*nlogn),m>n时，O(mnlogn); 对于斐波那契堆为O(mn + n*nlogn)
void johnson() {
    //create G' add S' s' = 0
    for (int i = 1; i <= graph.n; ++i) {
        graph.adj[0].push_back(E(i, 0));//w = 0
    }
    if (!bellman_ford(0)) {
        cout << "the input graph contains a negative-weight cycle" << endl;
        return;
    }
    //d(u)= shortest path from S to u,w'(u,v)=w(u,v)+dist(u)-dist(v) >= 0
    for (int u = 1; u <= graph.n; ++u) {
        for (int v = 0; v < graph.adj[u].size(); ++v) {
            graph.adj[u][v].w = graph.adj[u][v].w + dist[0][u] - dist[0][v];//update w'
        }
    }
    for (int u = 1; u <= graph.n; ++u) {
        dijkstra(u);
        for (int v = 1; v <= graph.n; ++v) {//更新所有从u出发到所有顶点的距离
            dist[u][v] = dist[u][v] - dist[0][u] + dist[0][v];//d'(u,v)=d(u,v)+dist(u)-dist(v)
        }
    }

}

void createGraph() {
    int u, v, k, w;
    cin >> graph.n >> graph.m;

    for (k = 1; k <= graph.m; ++k) {
        cin >> u >> v >> w;
        graph.adj[u].push_back(E(v, w));
    }
}

void print_shortest_path(int s, int v) {
    if (v == s) { cout << s << " "; return; }
    if (parent[s][v] == 0) { cout << "no path from " << s << " to " << v << endl; return; }
    print_shortest_path(s, parent[s][v]);
    cout << v << " ";
}
void print_path() {
    for (int s = 1; s <= graph.n; ++s) {
        cout << "start point=" << s << ":" << endl;
        for (int v = 1; v <= graph.n; ++v) {
            print_shortest_path(s, v);
            cout << ",dist=" << dist[s][v] << endl;
        }
        cout << endl;
    }
}

int main() {
    createGraph();
    johnson();
    print_path();
}

Floyd Warshall

　　动态规划算法。整体思想是考察i->j最短路径，对于中间节点1~k，k是最大下标，考察i->j中间是否会经过该节点k。如果不经过k，则最短路径可能经过中间节点1~k-1。如果经过k，则原问题化成两个子问题，i->k,k->j。
$$\begin{equation} d_{ij}^{(k)}= \left\{ \begin{aligned} w_{ij}, k=0 \\\ min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}),k>0 \end{aligned} \right. \end{equation}$$
　　该算法时间复杂度为\(O(V^3)\)，对于稠密图很有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
//节点编号1 ~ |V|
const int MAXV = 100 + 1;
const int INF = 1e5;

struct Graph {
    int A[MAXV][MAXV];
    int n;
    int m;
};
Graph graph;

vector<vector<int>> dist(MAXV, vector<int>(MAXV, INF)); // 距离矩阵，第一维是起始点,0编号存放S'到各个点的距离
vector<vector<int>> parent(MAXV, vector<int>(MAXV, 0));//前驱子图，第一维是起始点,初始化为0


void floyd_warshall() {
    //init
    for (int i = 1; i <= graph.n; ++i) {
        for (int j = 1; j <= graph.n; ++j) {
            dist[i][j] = graph.A[i][j];
        }
        dist[i][i] = 0;//自己到自己距离为0，非常重要！！再赋值一次
        
    }
    for (int k = 1; k <= graph.n; ++k) //k有n种选择
        for (int i = 1; i <= graph.n; ++i)
            for (int j = 1; j <= graph.n; ++j) { //考虑i->j,是否经过中间某个点k
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];//经过k更短
                    parent[i][j] = k;//i->j，经过k。记录中间节点。i->j: i->k,k->j. 
                }
            }
}

void createGraph() {
    int u, v, k, w;
    cin >> graph.n >> graph.m;
    for (int i = 1; i <= graph.n; ++i) {
        fill_n(graph.A[i], graph.n+1, INF);//记得初始化，重要！
        graph.A[i][i] = 0;//重要！
    }
    for (k = 1; k <= graph.m; ++k) {
        cin >> u >> v >> w;
        graph.A[u][v] = w;
    }
}


void print_shortest_path(int s, int v) {
    if (parent[s][v] == 0) { cout << v << ' '; return; }//s->v不需要经过任何中间点，则直接打印！
    print_shortest_path(s, parent[s][v]);
    print_shortest_path(parent[s][v], v);
}
void print_path() {
    for (int s = 1; s <= graph.n; ++s) {
        cout << "start point=" << s << ":" << endl;
        for (int v = 1; v <= graph.n; ++v) {
            if (dist[s][v] == INF) { cout << "no path from " << s << " to " << v << endl; continue; }
            cout << s << " ";
            print_shortest_path(s, v);
            cout << ",dist=" << dist[s][v] << endl;
        }
        cout << endl;
    }
}

int main() {
    createGraph();
    floyd_warshall();
    print_path();
}

坚持原创技术分享，您的支持将鼓励我继续创作！