码农场对图的几种初级算法做个总结，温故知新。
最短路问题
Bellman-Ford和Dijkstra的递推公式都是d[i] = min{d[j] + cost[i to j]}。
单源最短路之Bellman-Ford算法
适用于无原点s可达负圈的任意图，复杂度O(|V|*|E|)。
如果负圈存在的话，会陷入死循环。但是可以利用这一性质来判断是否有负圈：
#include <iostream>
using namespace std;
#define MAX_E 1024
// 从顶点from指向顶点to的权值为cost的边
struct edge
{
int from, to, cost;
edge(){}
edge(int from, int to, int cost)
{
this->from = from;
this->to = to;
this->cost = cost;
}
};
// 边
edge es[MAX_E];
// 最短距离
int d[MAX_E];
// V是顶点数，E是边数
int V, E;
// 求解从顶点s出发到所有点的最短距离
void shortest_path(int s)
{
memset(d, 0x3f, V * sizeof(int));
d[s] = 0;
while (true)
{
bool update = false;
for (int i = 0; i < E; ++i)
{
edge e = es[i];
if (d[e.from] != 0x3f3f3f3f && d[e.to] > d[e.from] + e.cost)
{
d[e.to] = d[e.from] + e.cost;
update = true;
}
}
if (!update)
{
break;
}
}
}
// 是否存在负圈
bool find_negative_loop()
{
memset(d, 0, sizeof(d));
for (int i = 0; i < V; ++i)
{
for (int j = 0; j < E; ++j)
{
edge e = es[j];
if (d[e.to] > d[e.from] + e.cost)
{
d[e.to] = d[e.from] + e.cost;
// 如果更新了V次，则存在负圈
if (i == V - 1)
{
return true;
}
}
}
}
return false;
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
// 测试数据
V = 7;
E = 20;
es[0] = edge(0, 1, 2);
es[1] = edge(0, 2, 5);
es[2] = edge(1, 2, 4);
es[3] = edge(1, 3, 6);
es[4] = edge(1, 4, 10);
es[5] = edge(2, 3, 2);
es[6] = edge(3, 5, 1);
es[7] = edge(4, 5, 3);
es[8] = edge(4, 6, 5);
es[9] = edge(5, 6, 9);
// 无向图必须重复一遍
es[10] = edge(1, 0, 2);
es[11] = edge(2, 0, 5);
es[12] = edge(2, 1, 4);
es[13] = edge(3, 1, 6);
es[14] = edge(4, 1, 10);
es[15] = edge(3, 2, 2);
es[16] = edge(5, 3, 1);
es[17] = edge(5, 4, 3);
es[18] = edge(6, 4, 5);
es[19] = edge(6, 5, 9);
// 测试数据结束
cout << "negative loop ? " << boolalpha << find_negative_loop() << endl;
shortest_path(0);
cout << d[V - 1] << endl;
system("pause");
return 0;
}
///////////////////////////End Sub//////////////////////////////////
单源最短路之Dijkstra算法
Bellman-Ford机械地遍历每一条边，浪费时间。Dijkstra算法每次循环都从最短距离已经确定的顶点出发，如果用堆储存最短距离的状态的话，复杂度降低为O(|E|log|V|)。这里的“最短距离已经确定”的前提是，没有负权重使得此最短距离变小，所以Dijkstra不能用于负边。举个例子说明Dijkstra为什么不能有负边：
1->2 2
1->3 100
3->2 -99
求从1开始的单源最短路的话会得到1->2最短路是2的错误结果。这是还是需要使用Bellman-Ford算法。
一份实现：
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
#define MAX_V 1024
// 从顶点from指向顶点to的权值为cost的边
struct edge
{
int to, cost;
edge(){}
edge(int to, int cost)
{
this->to = to;
this->cost = cost;
}
};
// first 最短路径，second顶点编号
typedef pair<int, int> P;
// 边
vector<edge> G[MAX_V];
// 最短距离
int d[MAX_V];
// V是顶点数，E是边数
int V, E;
// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
priority_queue<P, vector<P>, greater<P> > que;
memset(d, 0x3f, V * sizeof(int));
d[s] = 0;
que.push(P(0, s));
while (!que.empty())
{
P p = que.top(); que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); ++i)
{
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
// 测试数据
V = 7;
E = 20;
G[0].push_back(edge(1, 2));
G[1].push_back(edge(0, 2));
G[0].push_back(edge(2, 5));
G[2].push_back(edge(0, 5));
G[1].push_back(edge(2, 4));
G[2].push_back(edge(1, 4));
G[1].push_back(edge(3, 6));
G[3].push_back(edge(1, 6));
G[1].push_back(edge(4, 10));
G[4].push_back(edge(1, 10));
G[2].push_back(edge(3, 2));
G[3].push_back(edge(2, 2));
G[3].push_back(edge(5, 1));
G[5].push_back(edge(3, 1));
G[4].push_back(edge(5, 3));
G[5].push_back(edge(4, 3));
G[4].push_back(edge(6, 5));
G[6].push_back(edge(4, 5));
G[5].push_back(edge(6, 9));
G[6].push_back(edge(5, 9));
// 测试数据结束
dijkstra(0);
cout << d[V - 1] << endl;
system("pause");
return 0;
}
///////////////////////////End Sub//////////////////////////////////
路径还原
如果要求解最短路径途经的各点，只需定义一个prev[j]来记录最短路径上顶点j的前驱即可。
#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <iterator>
using namespace std;
#define MAX_V 1024
// 从顶点from指向顶点to的权值为cost的边
struct edge
{
int to, cost;
edge(){}
edge(int to, int cost)
{
this->to = to;
this->cost = cost;
}
};
// first 最短路径，second顶点编号
typedef pair<int, int> P;
// 边
vector<edge> G[MAX_V];
// 最短距离
int d[MAX_V];
// V是顶点数，E是边数
int V, E;
int prev_vertex[MAX_V]; // 最短路上的前驱顶点
// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
priority_queue<P, vector<P>, greater<P> > que;
memset(d, 0x3f, V * sizeof(int));
d[s] = 0;
que.push(P(0, s));
while (!que.empty())
{
P p = que.top(); que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); ++i)
{
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
prev_vertex[e.to] = v;
}
}
}
}
// 到顶点t的最短路
vector<int> get_path(int t)
{
vector<int> path;
for (; t != -1; t = prev_vertex[t])
{
path.push_back(t);
}
reverse(path.begin(), path.end());
return path;
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
prev_vertex[0] = -1;
// 测试数据
V = 7;
E = 20;
G[0].push_back(edge(1, 2));
G[1].push_back(edge(0, 2));
G[0].push_back(edge(2, 5));
G[2].push_back(edge(0, 5));
G[1].push_back(edge(2, 4));
G[2].push_back(edge(1, 4));
G[1].push_back(edge(3, 6));
G[3].push_back(edge(1, 6));
G[1].push_back(edge(4, 10));
G[4].push_back(edge(1, 10));
G[2].push_back(edge(3, 2));
G[3].push_back(edge(2, 2));
G[3].push_back(edge(5, 1));
G[5].push_back(edge(3, 1));
G[4].push_back(edge(5, 3));
G[5].push_back(edge(4, 3));
G[4].push_back(edge(6, 5));
G[6].push_back(edge(4, 5));
G[5].push_back(edge(6, 9));
G[6].push_back(edge(5, 9));
// 测试数据结束
dijkstra(0);
cout << d[V - 1] << endl;
auto path = get_path(V - 1);
copy(path.begin(), path.end(), ostream_iterator<int>(cout, " "));
cout << endl;
system("pause");
return 0;
}
///////////////////////////End Sub//////////////////////////////////
输出：
16 0 2 3 5 4 6 请按任意键继续. . .
任意两点之间的距离Floyd-Warshall算法
d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0
在只是用顶点0~k和i,j的情况下，记i到j的最短路径长度为d[k+1][i][j]，如果这次不经过顶点k那么d[k][i][j] = d[k-1][i][j]，否则d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]，两种情况取小值作为d的值。注意到第一个下标k是冗余的，于是忽略它。
Floyd-Warshall算法三重循环，实现起来非常简单。复杂度于是成为O(|V|3)；可以处理负边，如果需要判断图中是否存在负圈，只需检查d中是否有负数即可。
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_V 1024
int d[MAX_V][MAX_V]; // d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0
int V; // 顶点数
void warshall_floyd()
{
for (int k = 0; k < V; ++k)
{
for (int i = 0; i < V; ++i)
{
for (int j = 0; j < V; ++j)
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
// 测试数据
V = 7;
memset(d, 0x3f, V * MAX_V * sizeof(int));
d[0][1] = 2;
d[0][2] = 5;
d[1][2] = 4;
d[1][3] = 6;
d[1][4] = 10;
d[2][3] = 2;
d[3][5] = 1;
d[4][5] = 3;
d[4][6] = 5;
d[5][6] = 9;
// 无向图必须重复一遍
d[1][0] = 2;
d[2][0] = 5;
d[2][1] = 4;
d[3][1] = 6;
d[4][1] = 10;
d[3][2] = 2;
d[5][3] = 1;
d[5][4] = 3;
d[6][4] = 5;
d[6][5] = 9;
warshall_floyd();
cout << d[0][V - 1] << endl;
system("pause");
return 0;
}
///////////////////////////End Sub//////////////////////////////////
