注意！！！下面的模板有的并没有去设定具体的无法到达的极限值，也没有考虑极限相加爆表的情况，如果可以的话，最好还是把dis数组定义成long long
Floyd算法(仅仅四行的算法)
Floyd算法仅仅四行就能解决问题但是时间复杂度达到了感人的O(n^3)，唯一的有点是能够输出任意两点之间的最小路径，这或许是他唯一的用途了吧。
伪代码
初始化
赋值如果i==j为0其余为inf
建图
Floyd四行代码
输出
代码模板
#include <bits/stdc++.h>
using namespace std;
int G[10005][10005];
int main()
{
//n为节点数，m为边的条数
int n,m;
cin>>n>>m;
//初始化，如果i==j那么G[i][j]就是0
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
G[i][j]=i==j?0:999999999;
//建图
while(m--)
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
G[t1][t2]=t3;
}
//Floyd算法的核心，4行代码解决
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
//输出答案
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<G[i][j]<<" ";
cout<<endl;
}
return 0;
}
Floyd可以解决任意两个节点之间的最短路，而且在稀疏图有着还可以的时间复杂度
Dijkstra算法
无优化原始版本
时间复杂度的进一步的降低，能够算出源节点到各个节点之间的最短路
伪代码
初始化
赋值如果i==j为0其余为inf
建图
初始化dis数组与bk数组
bk[s]=1;
循环n次
寻找离要找节点最近的节点
bk[u]=1;
尝试每个节点是否能够被这个最近的节点松弛
循环结束
输出dis数组
代码模板
#include <bits/stdc++.h>
using namespace std;
int G[10010][10010];
int dis[10010];
int bk[10010];
int main()
{
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
G[i][j]=i==j?0:999999999;
while(m--)
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
G[t1][t2]=t3;
}
for(int i=1;i<=n;i++)
dis[i]=G[s][i];
memset(bk,0,sizeof(bk));
bk[s]=1;
for(int i=1;i<=n;i++)
{
int x,minn=999999999;
for(int j=1;j<=n;j++)
if(dis[j]<minn&&!bk[j])
minn=dis[x=j];
bk[x]=1;
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],dis[x]+G[x][j]);
}
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
复杂度O(n^2)
vector建图优化
因为我们用邻接矩阵建图很有可能会爆内存，所以可以采用vector数组建图优化。遇到较大的数据可以采用。
vector优化模板
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int to,cost;
};
vector<node> G[500005];
int bk[500005];
ll dis[500005];
const int inf=INT_MAX;
int main()
{
//freopen("data.in","r",stdin);
int m,n,s;
cin>>n>>m>>s;
while(m--)
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
node e;
e={t2,t3};
G[t1].push_back(e);
}
for(int i=1;i<=n;i++)
dis[i]=i==s?0:inf;
for(int i=1;i<=n;i++)
{
int x,y=inf;
for(int j=1;j<=n;j++)
if(!bk[j]&&dis[j]<=y)
y=dis[x=j];
bk[x]=1;
for(int j=0;j<G[x].size();j++)
dis[G[x][j].to]=min(dis[G[x][j].to],dis[x]+G[x][j].cost);
}
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
实际上根据题目的要求如果无法到达的话要进行各种的输出，最好定义dis数组为ll为妙
最终优化vector+优先队列
直接硬性把时间设置成MlogN
模板代码
#include <bits/stdc++.h>
using namespace std;
struct node //存入优先队列中的结构体
{
int num;
int cost;
bool operator < (const node&a) const
{
return cost>a.cost;
}
};
struct edge//存入vector中的
{
int to,cost;
};
int dis[10005];
int bk[10005];
const int inf=INT_MAX;
vector <edge> G[10005];
priority_queue <node> q;
int main()
{
int n,m,s;
cin>>n>>m>>s;
while(m--) //建图
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
edge e={t2,t3};
G[t1].push_back(e);
}
for(int i=1;i<=n;i++)//初始化dis数组
dis[i]=i==s?0:inf;
bk[s]=1;
q.push((node){s,0});
while(!q.empty())
{
node a=q.top();
q.pop();
if(dis[a.num]!=a.cost)//判断条件剪枝
continue;
bk[a.num]=1;
for(int i=0;i<G[a.num].size();i++)
if(!bk[G[a.num][i].to])
{
if(dis[G[a.num][i].to]>dis[a.num]+G[a.num][i].cost)
{
dis[G[a.num][i].to]=dis[a.num]+G[a.num][i].cost;
q.push((node){G[a.num][i].to,dis[G[a.num][i].to]});
}
}
}
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
Bellman-Ford算法（真的三行。。。。）
基本的思路与dijkstra差不多，但是能够解决负权图
伪代码
初始化
初始化dis数组
Bellman-Ford算法
输出dis数组
无优化版本
#include <bits/stdc++.h>
using namespace std;
int num[500005],to[500005],cost[500005];
long long dis[100005];
const int inf=INT_MAX;
int main()
{
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
cin>>num[i]>>to[i]>>cost[i];
for(int i=1;i<=n;i++)
dis[i]=i==s?0:inf;
for(int k=1;k<=n-1;k++)
for(int i=1;i<=m;i++)
dis[to[i]]=min(dis[to[i]],dis[num[i]]+cost[i]);
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
SPFA
近似于无敌的算法，但是对于解决非负权边的单源最短路还是用dij+优先队列优化得了
沙雕图
废话少说直接上模板
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int to,cost;
};
int dis[100005];
int bk[100005];
vector<edge> G[100005];
queue<int> q;
const int inf=INT_MAX;
int main()
{
int n,m,s;
cin>>n>>m>>s;
while(m--)
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
G[t1].push_back((edge){t2,t3});
}
for(int i=1;i<=n;i++)
dis[i]=i==s?0:inf;
q.push(s);
while(!q.empty())
{
int p=q.front();
q.pop();
bk[p]=0;
for(int i=0;i<G[p].size();i++)
{
if(dis[G[p][i].to]>dis[p]+G[p][i].cost)
{
dis[G[p][i].to]=dis[p]+G[p][i].cost;
if(!bk[G[p][i].to])
{
q.push(G[p][i].to);
bk[G[p][i].to]=1;
}
}
}
}
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
总结
如果每个节点之间的最小路径需要求出的话，那么还是用Floyd吧，对于非负图看n和m如果m都比n大了，那么最好还是老老实实的用Dijkstra+优先队列吧，如果出现负权图，那么还是老老实实SPFA