最短路也疯狂

最短路三种写法（Ford,Dijkstra【vector+有优先队列】,Floyd）小节

1.Ford(O(|V|*|E|))(可以判断是否有负环)
基本写法

#include<iostream>
#include<cstdio>
#include<cstring>
const int INF = 0x3f3f3f3f;
const int maxn = 1008;
using namespace std;

struct node{
    int u,v,w;//起点：U  终点：V   边权：W
}e[maxn];
int n,m;
int d[maxn];

int Ford_find_navegative_loop(){
    memset(d,0,sizeof(d));
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            node tmp = e[j];
            if(d[tmp.v] > d[tmp.u] + tmp.w){
                d[tmp.v] = d[tmp.u] + tmp.w;
                if(i == n - 1)  return 1;
            }
        }
    }
    return 0;
}

int cnt;
void add(int from,int to,int cost){
    e[cnt].u = from;
    e[cnt].v = to;
    e[cnt++].w = cost;
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        int a,b,c;
        for(int i = 1 ; i <= m ; i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);//双向边
        }
        int cas = Ford_find_navegative_loop();
        if(cas == 1)    cout<<"存在负环"<<endl;
        else    cout<<"不存在负环"<<endl;
    }
    return 0;
}
/*
3 3
1 2 -1
1 3 3
2 3 2
*/

2.Dijkstra + vector + 优先队列(O(|E|log|V|)) kuangbin带你飞专题四(HDU-2544)，这个是最经典简单的最短路问题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
const int maxn = 1008;
const int INF = 0x3f3f3f3f;
using namespace std;

struct node{
    int v,w;
    bool operator < (const node &a) const{
        return w > a.w;//重载：优先队列的默认优先级是大->小;而最短路需要小的先出来，所以重载
    }
};

priority_queue<node>q;
int m,n;
int vis[maxn],d[maxn];
vector<node>e[maxn];

void Dijkstra(){
    memset(vis,0,sizeof(vis));
    while(!q.empty())   q.pop();
    for(int i = 1; i <= n ; i++){
        d[i] = INF;
    }
    d[1] = 0;
    q.push(node{1,0});
    while(!q.empty()){
        node tmp = q.top();
        q.pop();
        int u = tmp.v;
        if(vis[u])  continue;
        vis[u] = 1;
        for(int i = 0 ; i < e[u].size() ; i++){
            int v = e[u][i].v;
            int w = e[u][i].w;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                q.push(node{v,d[v]});
            }
        }
    }
}

int main(){
    while(~scanf("%d%d",&n,&m) && (m + n)){
        int a,b,c;
        for(int i = 0 ; i < n ; i++)    e[i].clear();
        for(int i = 0 ; i < m ; i++){
            scanf("%d%d%d",&a,&b,&c);
            e[a].push_back(node{b,c});
            e[b].push_back(node{a,c});
        }
        Dijkstra();
        printf("%d\n",d[n]);
    }
    return 0;
}

3.Floyd（O(V^3）依旧是kuangbin带你飞的专题四（POJ-2253），刷专题好啊，刷专题才觉得自己学了点啥

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
const int maxn = 1008;
const int INF = 0x3f3f3f3f;
using namespace std;

int n;
double s[maxn][maxn];

pair<int,int>q[maxn];

double d(pair<int,int> x,pair<int,int> y){
    return (double)sqrt((double)((x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second)));
}

void floyd(){
    for(int k = 0 ; k < n ; k++){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(s[i][j] > max(s[i][k],s[k][j]))
                    s[i][j] = max(s[i][k],s[k][j]);
            }
        }
    }
    printf("Frog Distance = %.3f\n\n",s[0][1]);
}

int main(){
    int cas = 1;
    while(~scanf("%d",&n) && n){
        int a,b;
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d",&a,&b);
            q[i] = make_pair(a,b);
        }
        for(int i = 0 ; i < n - 1 ; i++){
            for(int j = i + 1 ; j < n ; j++){
                s[i][j] = s[j][i] = d(q[i],q[j]);
            }
        }
        printf("Scenario #%d\n",cas);
        floyd();
        cas++;
    }
    return 0;
}

小结

1. 一般来说，都不会用Ford来求最短路，求最短路最好是用Dijkstra,算法复杂度低一点，但是它是单源的最短路，就是只能从一个点出发，去找它到别的点的最短了距离；Ford用来判断是否有负环；Floyd是多源最短路，可以求任何点到任何点的最短距离；Dijkstra和Floyd都不能有负环。
2. Ford是找到比原来小的就更新，和Dijkstra的不同之处在于，Dijkstra是先从源点出发找最短的，只要不存在负边，找到的这个点就是源点到它的最短距离，不可能有别的点来更新它的值了，所以就可以用它这个点去更新别的点，逐步找到最小的。
3. emmmm，对了，还有一个是SPFA,没学，看了一下，那个算法复杂度不确定，个人感觉没有Dijkstra优秀（呀~，不喜勿喷，菜鸡我是这样觉得的）。个人感觉没有说清楚，先这样吧。欢迎大家评论交流。