原创于2017.04.03：最短路
1.多源的Floyd, 邻接矩阵实现，复杂度O（n^3），n<400;
2.单源Dijkstra，邻接矩阵实现，无负边，复杂度O（n^2），n<10000；
3.单源Dijkstra，邻接表实现，堆优化，无负边，复杂度O（E logE），点多边少；
4.单源bellman_ford，边集实现，可验负环，复杂度O（nE），nm<10^8；
5.单源SPFA，邻接表+队列实现，可验负环，复杂度 < O（nE）；
6.单源SPFA，邻接表+栈实现，可验负环，复杂度 < O（nE）；
专题练习：斌神的【最短路】
点击查看代码
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
/********Floyd********/
int const N=10000;
int const INF=99999999;
int w[N][N];
void init(int n)
{
memset(w,0,sizeof(w));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j)continue;
w[i][j]=INF;
}
}
void floyd(int n)
{
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
{
if(u==v)continue;
for(int i=1;i<=n;i++)
{
if(i==u||i==v)continue;
if(w[u][v]>w[u][i]+w[i][v])
w[u][v]=w[u][i]+w[i][v];
}
}
}
/************************/
/********Dijkstra********/
int const N=10000;
int const INF=99999999;
int w[N][N];
int dis[N],fa[N],b[N];
void dijkstra(int n,int s)
{
memset(b,0,sizeof(b));
memset(fa,-1,sizeof(fa));
for(int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
for(int j=0;j<n;j++)
{
int k=-1,mmin=INF;
for(int i=1;i<=n;i++)
if(!b[i]&&dis[i]<mmin)k=i,mmin=dis[i];
if(k==-1)break;
b[k]=1;
for(int i=1;i<=n;i++)
{
if(!b[i]&&dis[i]>dis[k]+w[k][i])
{
dis[i]=dis[k]+w[k][i];
fa[i]=k;
}
}
}
}
/*************************/
/*******Dijkstra_堆*******/
int const N=10000;
int const INF=99999999;
int dis[N],b[N],fa[N];
struct Node
{
int x;
int feet;
Node(int _x=0,int _feet=0):x(_x),feet(_feet){}
bool operator <(const Node &a)const
{
return feet>a.feet;
}
}an;
priority_queue<Node> q;
struct Eg
{
int v;
int w;
Eg(int _v=0,int _w=0):v(_v),w(_w){}
};
vector<Eg> E[N];
void addge(int u,int v,int w)
{
E[u].push_back(Eg(v,w));
}
void dijkstra(int n,int s)
{
memset(b,0,sizeof(b));
memset(fa,-1,sizeof(fa));
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
q.push(Node(s,0));
while(!q.empty())
{
an=q.top();q.pop();
if(b[an.x])continue;
b[an.x]=1;
int u=an.x;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
int w=E[u][i].w;
if(!b[v]&&dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;fa[v]=u;
q.push(Node(v,dis[v]));
}
}
}
}
/*************************/
/******bellman_ford*******/
int const N=10000;
int const INF=99999999;
int dis[N];
struct Eg
{
int u;
int v;
int w;
Eg(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};
vector<Eg> E;
int bellman(int n,int s)
{
for(int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
for(int j=0;j<n-1;j++)
{
int flag=1;
for(int i=0;i<E.size();i++)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
if(dis[E[i].v]>dis[E[i].u]+E[i].w)
{
dis[E[i].v]=dis[E[i].u]+E[i].w;
flag=0;
}
}
if(flag) return 1;
}
for(int i=0;i<E.size();i++)
if(dis[E[i].v]>dis[E[i].u]+E[i].w)return 0;
return 1;
}
/***************************/
/*********SPFA_队列*********/
int const N=10000;
int const INF=99999999;
int dis[N],b[N],cnt[N];
struct Eg
{
int v;
int w;
Eg(int _v=0,int _w=0):v(_v),w(_w){}
};
vector<Eg> E[N];
queue<int> q;
void addge(int u,int v,int w)
{
E[u].push_back(Eg(v,w));
}
int spfa(int n,int s)
{
memset(b,0,sizeof(b));
memset(cnt,0,sizeof(cnt));
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
q.push(s);b[s]=1;cnt[s]++;
while(!q.empty())
{
int u=q.front();q.pop();
b[u]=0;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dis[v]>dis[u]+E[u][i].w)
{
dis[v]=dis[u]+E[u][i].w;
if(!b[v])
{
q.push(v);b[v]=1;cnt[v]++;
if(cnt[v]>n) return 0;
}
}
}
}
return 1;
}
/***************************/
/*********SPFA_栈*********/
int const N=10000;
int const INF=99999999;
int dis[N],b[N],cnt[N];
struct Eg
{
int v;
int w;
Eg(int _v=0,int _w=0):v(_v),w(_w){}
};
vector<Eg> E[N];
stack<int> s;
void addge(int u,int v,int w)
{
E[u].push_back(Eg(v,w));
}
int spfa(int n,int s)
{
memset(b,0,sizeof(b));
memset(cnt,0,sizeof(cnt));
while(!s.empty())s.pop();
for(int i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
s.push(s);b[s]=1;cnt[s]++;
while(!s.empty())
{
int u=s.top();s.pop();
b[u]=0;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dis[v]>dis[u]+E[u][i].w)
{
dis[v]=dis[u]+E[u][i].w;
if(!b[v])
{
s.push(v);b[v]=1;cnt[v]++;
if(cnt[v]>n) return 0;
}
}
}
}
return 1;
}
/***************************/