JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
题目大意:求图上单点到单点之间的最短路。

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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理