題目大意：求圖上單點到單點之間的最短路。
題目分析：單源最短路問題是固定一個起點，求它到其他所有點的最短路的問題。終點也固定問題叫做兩點之間最短路問題。但是因為單源最短路問題的復雜度是一樣的，因此通常當作單源最短路問題來求解。
記從起點s出發到頂點i的最短距離為dist[i]。則下述等式成立。
dist[i] = min{dist[j]+(從j到i的邊的權值)|e=(j,i)∈E}
如果給定的圖是一個DAG，就可以按托不許給頂點編號，并利用這條遞推關系計算出dist。但是，如果圖中有圈，就無法利用這樣的關系進行計算。
在這種情況下，記當前到頂點i的最短距離為dist[i]，并設初值dist[s]=0，dist[i]=INF（足夠大的常數），再不斷使用這條地推關系式更新dist值，就可以算出新的dist。
只要途中不存在負圈，這樣的更新操作就是有限的。結束之后的最短操作就是所求的最短距離了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010, maxm = 4040;
int n, m;
struct Edge { int from, to, cost; } edge[maxm];
int V, E, dist[maxn];
void bellman_ford(int s) {
for(int i=0;i<V;i++) dist[i] = INF;
dist[s] = 0;
while(true) {
bool update = false;
for(int i=0;i<E;i++) {
Edge e = edge[i];
if(dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost) {
dist[e.to] = dist[e.from] + e.cost;
update = true;
}
}
if(!update) break;
}
}
int main() {
scanf("%d%d" , &m, &n);
V = n; E = 2 * m;
for(int i=0;i<E;i+=2) {
Edge e;
int from, to, cost;
scanf("%d%d%d" , &from, &to, &cost);
from --; to --;
edge[i].from = from;
edge[i].to = to;
edge[i].cost = cost;
edge[i+1].from = to;
edge[i+1].to = from;
edge[i+1].cost = cost;
}
bellman_ford(0);
printf("%d", dist[n-1]);
return 0;
}
這個算法叫做Bellman-Ford算法。如果在圖中不存在從s可達的負圈，那么最短路不會經過同一個頂點兩次（也就是說，最多通過|V|-1次），while(true)的循環最多經過|V|-1次，因此，復雜度是O(VE)。反之，如果存在從s可達的負圈，那么在第|V|次循環中也會更新dist的值，因此也可以用這個性質來檢查負圈。如果一開始對所有的i，都把dist[i]設為0，那么可以檢查出所有的負圈。
bool find_negetive_loop() {
memset(dist, 0, sizeof(dist));
for(int i=0;i<V;i++) {
for(int j=0;j<E;j++) {
if(dist[e.to] > dist[e.from] + e.cost) {
dist[e.to] = dist[e.from] + e.cost;
if(i == V-1) return true;
}
}
}
return false;
}
posted on 2015-02-13 19:32
JulyRina 閱讀(232)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告