題目大意：求圖上單點(diǎn)到單點(diǎn)之間的最短路。
題目分析：單源最短路問題是固定一個(gè)起點(diǎn)，求它到其他所有點(diǎn)的最短路的問題。終點(diǎn)也固定問題叫做兩點(diǎn)之間最短路問題。但是因?yàn)閱卧醋疃搪穯栴}的復(fù)雜度是一樣的，因此通常當(dāng)作單源最短路問題來求解。
記從起點(diǎn)s出發(fā)到頂點(diǎn)i的最短距離為dist[i]。則下述等式成立。
dist[i] = min{dist[j]+(從j到i的邊的權(quán)值)|e=(j,i)∈E}
如果給定的圖是一個(gè)DAG，就可以按托不許給頂點(diǎn)編號，并利用這條遞推關(guān)系計(jì)算出dist。但是，如果圖中有圈，就無法利用這樣的關(guān)系進(jìn)行計(jì)算。
在這種情況下，記當(dāng)前到頂點(diǎn)i的最短距離為dist[i]，并設(shè)初值dist[s]=0，dist[i]=INF（足夠大的常數(shù)），再不斷使用這條地推關(guān)系式更新dist值，就可以算出新的dist。
只要途中不存在負(fù)圈，這樣的更新操作就是有限的。結(jié)束之后的最短操作就是所求的最短距離了。
#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;
}
這個(gè)算法叫做Bellman-Ford算法。如果在圖中不存在從s可達(dá)的負(fù)圈，那么最短路不會(huì)經(jīng)過同一個(gè)頂點(diǎn)兩次（也就是說，最多通過|V|-1次），while(true)的循環(huán)最多經(jīng)過|V|-1次，因此，復(fù)雜度是O(VE)。反之，如果存在從s可達(dá)的負(fù)圈，那么在第|V|次循環(huán)中也會(huì)更新dist的值，因此也可以用這個(gè)性質(zhì)來檢查負(fù)圈。如果一開始對所有的i，都把dist[i]設(shè)為0，那么可以檢查出所有的負(fù)圈。
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 閱讀(237)
評論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告