最短路

以下部分内容转载自http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

Floyed

时间复杂度：$O(N^3)$

这复杂度……也只有走投无路之时会用到了

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=100;
int head[MAXN+1],ecnt;
struct node{int to,next,dis;} edge[MAXN+1];
int dis[MAXN+1][MAXN+1];
void add(int x,int y,int qz)
{
    ecnt++;
    edge[ecnt].to=y;
    edge[ecnt].next=head[x];
    head[x]=ecnt;
    dis[x][y]=qz;
}
bool lt(int x,int y)
{
    for(node redge=edge[head[x]];;redge=edge[redge.next])
    {
        if(redge.to==y) return true;
        if(!redge.next) break;
    }
    return false;
}
int m,n;
void floyed()
{
    memset(dis,0x7fffffff,sizeof(dis));
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
}

Dijkstra

时间复杂度$O(Nlog_2N)$

复杂度低且稳定，但不能处理负边权图，最重要的是手写堆优化的Dijkstra洋洋洒洒上百行，易写错

其实Dijkstra与SPFA十分相似，只是Dijkstra通过贪心法减少了不必要的松弛操作

思路：

• struct dat中存一个节点的目前最小路径长度和节点的标号
• 以dat为元建立小根堆
• 每次从小根堆取出一个不在S中的节点u，根据小根堆的性质，可以保证u是当前不在S中的点中最短路长度最小的点
• 搜索与其相邻的不在S中的点进行松弛、入堆
• 对每个节点进行过对u的此操作后，dis数组即为从v0出发到每个点的最短路

示例：

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int  MAXINT = 2147483647;
const int MAXN = 1e4,MAXM=5e5;
int dis[MAXN];
int N,M,s;
bool S[MAXN];  
int head[MAXN+1],ecnt;
struct node{int next,to,value;} e[MAXM+1];
void add(int x,int y,int z){ecnt++,e[ecnt].to=y,e[ecnt].next=head[x],head[x]=ecnt,e[ecnt].value=z;}
struct dat{int v,id;} heap[2*MAXN+1];int heapSize;
void put(dat x)
{
    int now,next;
    heap[++heapSize] = x;
    now = heapSize;
    while(now > 1)
    {
        next=now >> 1;
        if(heap[now].v >= heap[next].v)break;
        swap(heap[now],heap[next]);
        now = next;
    }
}
dat get()
{
    int now,next;
    dat res;
    res = heap[1];
    heap[1]=heap[heapSize--];
    now = 1;
    while(now * 2 <= heapSize)
    {
        next = now * 2;
        if(next < heapSize && heap[next+1].v < heap[next].v)next++;
        if(heap[now].v <= heap[next].v) break;
        swap(heap[now],heap[next]);
        now = next;
    }
    return res;
}
void Dijkstra(int v0)
{
    int i;
    for(i=1;i<=N;i++) dis[i]=MAXINT;                                
    memset(S,false,sizeof(S));
    for(int tmp=head[v0];tmp;tmp=e[tmp].next)
    {
        dis[e[tmp].to]=e[tmp].value;
        dat x;
        x.id=e[tmp].to,x.v=dis[e[tmp].to];
        put(x);
    }
    dis[v0] = 0;
    S[v0] = true;
    for(i=2; i<=N; i++)
    {
        int u;
        do u=get().id;
        while(S[u]);
        S[u] = true;
        for(int tmp=head[u];tmp;tmp=e[tmp].next)
            if(!S[e[tmp].to])
                if(dis[u]+e[tmp].value<dis[e[tmp].to])
                {
                    dis[e[tmp].to]=dis[u]+e[tmp].value;
                    dat x;
                    x.v=dis[e[tmp].to],x.id=e[tmp].to;
                    put(x);
                }
    }
}

SPFA

时间复杂度：$O(NM)$
不太稳定，但能处理负边权图

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXINT=2147483647;
const int MAXN=10000,MAXM=500000;
int n,m,s;
int head[MAXN+1],ecnt;
struct node{int to,next,value;} edge[MAXM+1];
void add(int x,int y,int z)ecnt++,edge[ecnt].to=y,edge[ecnt].next=head[x],head[x]=ecnt,edge[ecnt].value=z;}
bool vis[MAXN+1];
int dis[MAXN+1],queue[2*MAXN+5];
int SPFA(int v0)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=MAXINT;
    dis[v0]=0;      
    vis[v0]=true;
    int h=0,t=1;
    queue[t]=v0;
    while(h<t)
    {
        h=(h+1)%(2*n+5);//循环队列出队
        int u=queue[h];
        vis[u]=false;
        for(int tmp=head[u];tmp;tmp=edge[tmp].next)
            if(dis[edge[tmp].to]>dis[u]+edge[tmp].value)
            {
                dis[edge[tmp].to]=dis[u]+edge[tmp].value;
                if(!vis[edge[tmp].to])
                {
                    vis[edge[tmp].to]=true;
                    t=(t+1)%(2*n+5);//循环队列入队
                    queue[t]=edge[tmp].to;
                }
            }
    }
}
int main()
{
    freopen("spfa.in","r",stdin);
    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }//读入
    SPFA(s);
    for(int i=1;i<n;i++) cout<<dis[i]<<" ";//输出
    cout<<dis[n]<<endl;
    return 0;
}