最短路(牢记各个算法的时间复杂度)
1.单源最短路 只有一个起点
求一个点到其他的最短路,从1号点到n号点的最短路
朴素迪杰斯特拉算法适用于稀疏图(边与点一个级别)
堆优化版的迪杰斯特拉算法适用于稠密图(边与点的平方一个级别 ![]
2.多源汇最短路 有多个起点
任意两个点求其最短路
本题有500个点,10万条边,是稠密图,可以用邻接矩阵来写
朴素迪杰斯特拉算法步骤:
1.每次从未标记的结点中选择距离出发点最近的结点,标记,收录到最优路径的集合中
dist[1]=0;//1号点距离为0
for(int i=1;i<=n;i++)//计算每个点的距离
{ //找最短距离的点
int t=-1;
for(int j=1;j<=n;j++)
{
if(!used[j]&&(t==-1||dist[t]>dist[j]))//若当前点未收录且不是最短的
{
t=j;
}
}
//将t加到集合中去
used[t]=true;
2.计算刚加入的结点A到结点B的距离(不包含标记的结点)若结点A的距离+结点A到结点B的距离<结点B的距离,就更新结点B的距离
//更其它点的距离
for(int i=1;i<=n;i++)
{
dist[i]=min(dist[i],dist[t]+f[t][i]);
}
代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int f[N][N];//邻接矩阵
bool used[N];//收录最优路径点
int dist[N];//每个点到起始点的距离
int main()
{
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof f);
for(int i=1;i<=m;i++)
{
int a,b,z;
scanf("%d%d%d",&a,&b,&z);
f[a][b]=min(f[a][b],z);//若有重边则直接保留最短的边
}
memset(dist,0x3f,sizeof dist);
dist[1]=0;//1号点距离为0 (1)
for(int i=1;i<=n;i++)//计算每个点的距离
{ //找最短距离的点
int t=-1;
for(int j=1;j<=n;j++)
{
if(!used[j]&&(t==-1||dist[t]>dist[j]))//若当前点未收录且不是最短的,不知道如何进入一个步骤时可以用这个方法
{
t=j;
}
}
//将t加到集合中去
used[t]=true;
//更其它点的距离
for(int i=1;i<=n;i++)
{
dist[i]=min(dist[i],dist[t]+f[t][i]); (1)是dis[t]
}
}
if(dist[n]==0x3f3f3f3f)puts("-1");
else
printf("%d",dist[n]);
return 0;
}