Dijkstra算法主要在非负权图中求最短路，朴素做法O(n^2),堆优化O((m+n)logn),前者在稠密图(m>=n^2)中效率较高，后者在稀疏图中效率较高。SPFA算法(Bellman-Ford算法队列优化)在一般情况下效率较高，但在某些特殊情况下可能退化到O(n*m)(SPFA已经死了),可用于负权图。
//朴素Dijkstra算法
#include<iostream>
#define maxn 200500
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int v,w,nxt;
}e[maxn];
int h[maxn],nxt[maxn],tot=0,dis[maxn],vis[maxn];
int n,m,s;
void add(int u,int v,int w){
e[++tot]={v,w,h[u]};
h[u]=tot;
}
void dijkstra(){
for(int i=0;i<=n;++i){
dis[i]=inf;
vis[i]=0;
}
dis[s]=0;
for(int i=1;i<=n;++i){
int u=-1,min_d=inf;
for(int j=1;j<=n;++j){
if(!vis[j]&&dis[j]<min_d){
min_d=dis[j];
u=j;
}
}
if(u==-1||min_d==inf) break;
vis[u]=1;
for(int j=h[u];j>0;j=e[j].nxt){
int v=e[j].v;
int w=e[j].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
}
//堆优化Dijkstra算法
#include<iostream>
#include<vector>
#include<queue>
#define maxn 200500
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int v,w,nxt;
}e[maxn];
struct node{
int d,u;
bool operator <(const node&x)const{
return d>x.d;
}
};
int h[maxn],nxt[maxn],tot=0,dis[maxn],vis[maxn];
int n,m,s;
void add(int u,int v,int w){
e[++tot]={v,w,h[u]};
h[u]=tot;
}
void dijkstra(){
for(int i=0;i<=n;++i){
dis[i]=inf;
}
dis[s]=0;
priority_queue<node> q;
q.push({0,s});
while(!q.empty()){
int u=q.top().u;
int d=q.top().d;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];i>0;i=e[i].nxt){
int v=e[i].v;
int w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=d+w;
q.push({dis[v],v});
}
}
}
}
//SPFA算法
#include<iostream>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
#define maxn 200010
using namespace std;
long long dis[maxn],h[maxn];
bool vis(maxn);
int tot=0,s,n,m;
struct edge{
int v,w,nxt;
}e[maxn];
void add(int u,int v,int w){
e[++tot]={v,w,h[u]};
h[u]=tot;
}
void spfa(){
queue<int> q;
for(int i=1;i<=n;++i){
dis[i]=inf;
}
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=h[u];i>0;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}