题目大意：求图上单点到单点之间的最短路。
题目分析：单源最短路问题是固定一个起点，求它到其他所有点的最短路的问题。终点也固定问题叫做两点之间最短路问题。但是因为单源最短路问题的复杂度是一样的，因此通常当作单源最短路问题来求解。
记从起点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 阅读(219)
评论(0) 编辑 收藏 引用 所属分类:
解题报告