今天是寒假的最后一天，不知道干点什么事情才更有意义，于是想到把自己看过的图论的算法写一下吧！就算做是给别人的一个参考和自己的一个总结。
为了节省时间，不对该问题做太细致的介绍，也就是说这篇日志适合于已经基本了解最短路径算法的读者来看。
1、Dijkstra（迪杰斯克拉）算法
适用问题：该算法适用于解决
①、单源最短路径：已知图G=(V,E)，我们希望找出从给定某结点S∈V到V中每个结点的最短路径。
②、边权非负
该算法的主要思想是：
①、设定一个集合Set，对任意结点t∈V，若已知t到s的最短路径，则将 t 放入Set。
②、到s最近的那个结点肯定和s有边直接相连，不妨设该点为p。p到s所走的最短路径必然是走p和s相连的那条边
③、到s次近的那个结点q如何到s呢？要么直接走q与s相连的那条边，要么先到②中的p,然后到s
④、到s的最短距离是第三长的那个，如何到s呢？无非有三种情况：直接到s，先到p然后到s，先到q然后走q到s走的最短路径
⑤、其他的结点类比②③④可知
算法代码实现：
①、图用邻接矩阵表示：（O(n^2)）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 20;
//node numbers start from 1
int graph[maxn][maxn];
int m, n;//the numbers of edges and nodes
bool Set[maxn];
int dis[maxn];
int pre[maxn];
void Dijkstra(int s)
{
//initialize
for(int i = 1; i <= n; i ++)
{
Set[i] = (i == s ? true : false);
dis[i] = (i == s ? 0 : graph[s][i]);
pre[i] = (i == s ? 0 : s);
}
for(int i = 0; i < n - 1; i ++)
{
int min = INF, minn;
for(int j = 1; j <= n; j ++) if(!Set[j])
{
if(min >= dis[j])
{
min = dis[j]; minn = j;
}
}
Set[minn] = true;
for(int j = 1; j <= n; j ++) if(!Set[j])
{
if(dis[j] > min + graph[minn][j])
{
dis[j] = min + graph[minn][j];
pre[j] = minn;
}
}
}
}
void print_path(int v)
{
if(!v) return ;
print_path(pre[v]);
printf("%d ", v);
}
int main(void)
{
freopen("f:\\code\\file\\data.txt", "r", stdin);
scanf("%d%d", &m, &n);
//initialize the graph
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
graph[i][j] = (i == j ? 0 : INF);
//input the graph
for(int i = 0; i < m; i ++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = w;
}
//call the dijkstra algorithm
Dijkstra(1);
//output the result
for(int i = 1; i <= n; i ++)
{
print_path(i);
printf("\n%d\n", dis[i]);
}
return 0;
}
②、图用邻接表表示（适用于图中有重边的情况）（O(n^2)）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
const int maxn = 20;
const int INF = 0x3f3f3f3f;
struct Edge
{
int from, to, weight;
};
vector<Edge> edges;
//the nodes numbers start from 1
vector<int> G[maxn];//G[i][j] means the j-th edge of node i
int n, m;
int Set[maxn], dis[maxn], pre[maxn];
void Dijkstra(int s)
{
for(int i = 1; i <= n; i ++)
{
Set[i] = false;
dis[i] = (i == s ? 0 : INF);
pre[i] = (i == s ? 0 : s);
}
for(int i = 0; i < n; i ++)
{
int min = 0;
for(int j = 1; j <= n; j ++) if(!Set[j])
{
if(min == 0) min = j;
else if(dis[j] < dis[min]) min = j;
}
Set[min] = true;
for(int j = 0; j < G[min].size(); j ++)
{
int v = edges[G[min][j]].to;
int w = edges[G[min][j]].weight;
if(dis[v] > dis[min] + w)
dis[v] = dis[min] + w;
}
}
}
void print_path(int v)
{
if(!v) return;
print_path(pre[v]);
printf("%d ", v);
}
int main(void)
{
freopen("f:\\code\\file\\data.txt", "r", stdin);
scanf("%d%d", &m, &n);
//input the graph
while(m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edges.push_back((Edge){u, v, w});
G[u].push_back(edges.size() - 1);
}
Dijkstra(1);
for(int i = 1; i <= n; i ++)
{
print_path(i);
printf("\n%d\n", dis[i]);
}
return 0;
}
③、用优先队列优化后的实现代码(O(mlogn))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 20;
const int INF = 0x3f3f3f3f;
struct Edge
{
int from, to, weight;
};
vector<Edge> edges;
vector<int> G[maxn];
int m, n;
int Set[maxn], dis[maxn], pre[maxn];
void Dijkstra(int s)
{
for(int i = 1; i <= n; i ++)
{
dis[i] = (i == s ? 0 : INF);
Set[i] = false;
pre[i] = (i == s ? 0 : s);
}
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > q;
q.push(make_pair(dis[s], s));
while(!q.empty())
{
pii u = q.top(); q.pop();
int x = u.second;
if(Set[x]) continue;
Set[x] = 1;
for(int i = 0; i < G[x].size(); i ++)
{
int v = edges[G[x][i]].to;
int w = edges[G[x][i]].weight;
if(dis[v] > dis[x] + w)
{
dis[v] = dis[x] + w;
q.push(make_pair(dis[v], v));
pre[v] = x;
}
}
}
}
void print_path(int v)
{
if(!v) return;
print_path(pre[v]);
printf("%d ", v);
}
int main(void)
{
freopen("f:\\code\\file\\data.txt", "r", stdin);
//input the graph
scanf("%d%d", &m, &n);
while(m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edges.push_back((Edge){u, v, w});
G[u].push_back(edges.size() - 1);
}
Dijkstra(1);
for(int i = 1; i <= n; i ++)
{
print_path(i);
printf("\n%d\n", dis[i]);
}
return 0;
}
2、Bellman-Ford（贝尔曼-福特）算法
适用问题：该算法适用时需满足一下条件
①、单源最短路径
②、边权取值正负都可以，但是图中不能包含权值和为负数的圈
算法的主要思想：
①、注意到：最短路径的长度最大为n-1
②、定义状态d(i,j,k)代表结点i到结点j最多经过k条边的最短距离
③、状态转移方程d(i, j, k) = min{d(i, q, k - 1) + e(q,i) | e(q, i)
∈ E}
实现代码：
①、图用邻接表表示（O(nm)），如果用邻接矩阵的话效率会变低
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 20;
const int INF = 0x3f3f3f3f;
struct Edge
{
int from, to, weight;
};
vector<Edge> edges;
vector<int> G[maxn];
int m, n;
int dis[maxn], pre[maxn];
void Bellman_Ford(int s)
{
for(int i = 1; i <= n; i ++)
{
dis[i] = (i == s ? 0 : INF);
pre[i] = (i == s ? 0 : s);
}
for(int k = 0; k < n - 1; k ++)
{
for(int i = 0; i < edges.size(); i ++)
{
int u = edges[i].from, v = edges[i].to, w = edges[i].weight;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pre[v] = u;
}
}
}
}
void print_path(int v)
{
if(!v) return;
print_path(pre[v]);
printf("%d ", v);
}
int main(void)
{
freopen("f:\\code\\file\\data.txt", "r", stdin);
//input the graph
scanf("%d%d", &m, &n);
while(m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edges.push_back((Edge){u, v, w});
G[u].push_back(edges.size() - 1);
}
Bellman_Ford(1);
for(int i = 1; i <= n; i ++)
{
print_path(i);
printf("\n%d\n", dis[i]);
}
return 0;
}
②、用FIFO优化之后，最坏时还是O(nm)，不过一般效率要好些
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 20;
const int INF = 0x3f3f3f3f;
struct Edge
{
int from, to, weight;
};
vector<Edge> edges;
vector<int> G[maxn];
int m, n;
int dis[maxn], pre[maxn];
void Bellman_Ford(int s)
{
for(int i = 1; i <= n; i ++)
{
dis[i] = (i == s ? 0 : INF);
pre[i] = (i == s ? 0 : s);
}
queue<int> q;
q.push(s);
bool inq[maxn];
memset(inq, false, sizeof(inq));
inq[s] = true;
while(!q.empty())
{
int x = q.front(); q.pop();
inq[x] = false;
for(int i = 0; i < G[x].size(); i ++)
{
int u = edges[G[x][i]].from, v = edges[G[x][i]].to, w = edges[G[x][i]].weight;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pre[v] = u;
if(!inq[v])
{
q.push(v);
inq[v] = true;
}
}
}
}
}
void print_path(int v)
{
if(!v) return;
print_path(pre[v]);
printf("%d ", v);
}
int main(void)
{
freopen("f:\\code\\file\\data.txt", "r", stdin);
scanf("%d%d", &m, &n);
while(m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edges.push_back((Edge){u, v, w});
G[u].push_back(edges.size() - 1);
}
Bellman_Ford(1);
for(int i = 1; i <= n; i ++)
{
print_path(i);
printf("\n%d\n", dis[i]);
}
return 0;
}
3、Floyd（佛洛依德算法）
使用条件：
①、所有顶点之间的最短路径
②、边权即可为正，也可为负
主要思想：
Floyd算法的主要思想和Bellman_Ford算法有异曲同工之妙，都是基于递推的（我感觉就是动态规划）
①、注意到对于任意一条最短路径，该条路径所经过的结点的编号不会超出1~n这n种可能。
②、设状态d(i, j, k)表示结点i到结点j的满足某个特定条件的最短路径的长度，该条件为：最短路径上出去起始点外的结点的编号最大不会超过k
③、状态转移方程为：d(i, j, k) = min{d(i, j, k - 1), d(i, k, k - 1) + d(k, j, k - 1)}
实现代码：
图用邻接矩阵表示， 算法的复杂度为O(n^3)，代码写起来也比较简单，我感觉原因就是状态设计的好
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int maxn = 20;
const int INF = 0x3f3f3f3f;
//the node numbers start from 1
int m, n;
int dis[maxn][maxn];//dis[i][j] means the distance of the shortest path from node i to node j
int pre[maxn][maxn];// pre[i][j] means the previous node of node i on the shortest path which from i to j
void print_path(int v, int s)
{
if(!v) return ;
print_path(pre[v][s], s);
printf("%d ", v);
}
int main(void)
{
freopen("f:\\code\\file\\data.txt", "r",stdin);
scanf("%d%d", &m, &n);
//initialize
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j++)
{
dis[i][j] = (i == j ? 0 : INF);
pre[i][j] = (i == j ? 0 : j);
}
}
while(m --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
dis[u][v] = w;
}
//recurence
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(dis[i][j] > dis[i][k] + dis[k][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
pre[i][j] = pre[i][k];
}
// output the paths
for(int i = 1; i <= n; i ++)
{
print_path(i, 1);
printf("\n%d\n", dis[i][1]);
}
return 0;
}