最短路径

单源最短路之Dijkstra算法

所谓“单源最短路”是指只有唯一起点的最短路问题。常用的有朴素的Dijkstra算法写法和加了堆优化的写法，分别对应于稀疏图和稠密图的情况。

朴素的dijkstra算法，复杂度为O(V²)。

 1 const int INF = INT_MAX;  
 2 int d[N],vis[N];  
 3 int w[N][N];  
 4   
 5 void dijkstra(int s, int n)  
 6 {  
 7     memset(vis,0,sizeof(vis));  
 8     for(int i=1; i<=n; i++) d[i] = (i==s ? 0 : INF);  
 9     for(int i=1; i<=n; i++) {  
10         int x,m = INF;  
11         for(int j=1; j<=n; j++)  
12             if(!vis[j] && d[j]<m)  
13             m = d[x=j];  
14         vis[x] = 1;  
15         for(int j=1; j<=n; j++)  
16             if(d[j] < d[x]+w[x][j])  
17             d[j] = d[x] + w[x][j];  
18     }  
19 }

View Code

使用邻接表和优先队列优化的Dijkstra算法，复杂度为O(ElogV)，因此它适用于E远小于V²的稀疏图。

 1 const int INF = INT_MAX;  
 2 struct Edge {  
 3     int from, to, w;  
 4     Edge(){}  
 5     Edge(int a, int b, int c):from(a),to(b),w(c){}  
 6 };  
 7 vector<Edge>edges;  
 8 vector<int>G[N];  
 9 void AddEdge(int from, int to, int w)  
10 {  
11     edges.push_back(Edge(from,to,w));  
12     edges.push_back(Edge(to,from,w));  
13     int m = edges.size();  
14     G[from].push_back(m-2);  
15     G[to].push_back(m-1);  
16 }  
17 int vis[N],d[N],w[N][N];  
18 typedef pair<int,int> pii;  
19 priority_queue<pii,vector<pii>,greater<pii> >q;  
20 void dijkstra(int s, int n)  
21 {  
22     memset(vis,0,sizeof(vis));  
23     for(int i=1; i<=n; i++) d[i] = (i==s ? 0 : INF);  
24     while(!q.empty()) q.pop();  
25     q.push(make_pair(d[s],s));  
26     while(!q.empty()) {  
27         pii u = q.top(); q.pop();  
28         int x = u.second;  
29         if(vis[x]) continue;  
30         vis[x] = 1;  
31         for(int i=0; i<G[x].size(); i++) {  
32            Edge &e = edges[G[x][i]];  
33            if(d[e.to] > d[x] + e.w)  
34                d[e.to] = d[x] + e.w,  
35                q.push(make_pair(d[e.to],e.to));  
36         }  
37     }  
38 }  
39

View Code

单源最短路之Bellman-Ford 算法

对于带负权边的图，Dijkstra算法便无能为力了，而Bellman-Ford算法可以解决这个问题。

Bellman-Ford算法的一般写法也有两种，朴素式写法和使用FIFO队列优化的写法。

朴素的Bellman-Ford算法，复杂度为O(VE)。

 1 int u[M],v[M],w[M];  
 2 int d[N];  
 3 bool BF(int s, int n, int m)  //s:源点 n:点个数 m:边个数  
 4 {  
 5     for(int i=1; i<=n; i++) d[i] = (i==s ? 0 : INF);  
 6     for(int k=1; k<n; k++) {    //n-1次松弛  
 7         for(int i=1; i<=m; i++) //检查每条边  
 8         {  
 9             int x = u[i], y = v[i];  
10             if(d[x] < INF) d[y] = min(d[y],d[x]+w[i]);  
11         }  
12     }  
13     for(int k=1; k<=n; k++) {  //判负环  
14         for(int i=1; i<=m; i++)  
15         {  
16             int x = u[i], y = v[i];  
17             if(d[x] < INF && d[y] > d[x] + w[i])  
18                 return false;  
19         }  
20     }  
21     return true;  
22 }

View Code

1994年，西南交通大学的段凡丁发表了SPFA算法，其实质是使用FIFO队列优化后的Bellman-Ford算法。其论文指出该SPFA算法的时间复杂度可降至O(KE)，E指边的个数，而K是一个很小的常数，但他对该复杂度的证明是不严谨甚至是错误的。事实上，在Bellman算法的论文中已有这方面的内容。实践中，该算法的效果很不稳定，也没有得到国际上的认可。

 1 int inq[N],d[N];  
 2 int sum[N];  //记录点出入队列的次数  
 3 vector<Edge>edges;  
 4 vector<int>G[N];  
 5 bool BF(int s, int n)  
 6 {  
 7     queue<int>q;  
 8     for(int i=1; i<=n; i++) d[i] = (i==s ? 0 : INF);  
 9     memset(inq,0,sizeof(inq));  
10     memset(sum,0,sizeof(sum));  
11     sum[s] = 1;  
12     q.push(s);  
13     while(!q.empty()) {  
14         int x = q.front(); q.pop();  
15         inq[x] = 0;  
16         for(int i=0; i<G[x].size(); i++) {  
17             Edge &e = edges[G[x][i]];  
18             if(d[e.to] > d[x] + e.w) {  
19                 d[e.to] = d[x] + e.w;  
20                 if(!inq[e.to]) {  
21                     if(++sum[e.to] == n) return false;  
22                     inq[e.to] = 1;  
23                     q.push(e.to);  
24                 }  
25             }  
26         }  
27     }  
28     return true;  
29 }  
30

View Code

Floyd算法

Floyd算法可以求出图中任意两点之间的最短路径且不管边权是否为负，复杂度O(V³)。

1 int d[N][N];  
2 void Floyed(int n)  
3 {  
4     for(int k=1; k<=n; k++)   
5         for(int i=1; i<=n; i++)  
6             for(int j=1; j<=n; j++)  
7             if(d[[i][k]!=INF && d[k][j]<INF)  
8             d[i][j] = min(d[i][j],d[i][k]+d[k][j]);  
9 }

View Code

--Floyd算法应用之最小环

根据Floyd算法的思路，我们可以在求出最短路的同时得到该图中的最小环，即路径最短的环形线路。

Floyed算法是按照点的编号增加的顺序更新最短路的，假设环的最大号点是u，相邻两点为i,j,则在用u点更新 d[i][j]前，d[i][j] = w[i][u] + w[u][j],一定是一个环。

 1 int d[N][N],w[N][N];  
 2 void MinCircle(int n)  
 3 {  
 4     for(int k=1; k<=n; k++)   
 5     {  
 6         for(int i=1; i<=n; i++)  //最小环判定  
 7             for(int j=1; j<=n; j++)  
 8             if(d[i][j]!=INF && w[i][k]!=INF && w[k][j]!=INF  
 9                && d[i][j] + w[i][k] + w[k][j] < mincircle)  
10                mincircle = d[i][j] + w[i][k] + w[k][j];  
11         for(int i=1; i<=n; i++)  //Floyed部分  
12             for(int j=1; j<=n; j++)  
13             if(d[i][k]!=INF && d[k][j]!=INF)  
14             d[i][j] = min(d[i][j],d[i][k]+d[k][j]);  
15     }  
16 }

View Code