最短路

firstlight Lv2

从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。

最短路算法根据应用场景,可选用Dijkstra算法、spfa算法和Floyd算法

1.Dijkstra 算法:

算法是一种基于贪心的单源最短路算法,有朴素与堆优化两种

证明:

first–朴素:

应用场景:

用于稠密图,时间复杂度,稠密图中用堆优化版本效率较低,不宜使用

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int dist[N];                                      // 储存到每个节点的最短路径
int n, m; // 节点的数量和边的条数
int g[N][N]; // 图的信息
bool st[N]; // 每个节点的状态(走过或未走过)
int Dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0; // 1到1的路径长为0
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j])) // 查询图中的未被标记的(即未确定的)点到1的路径最短的点
t=j;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]); // 更新图中的每一个点
st[t]=true; // 标记
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c); // 记录a,b间最短的距离
}
}

second–堆优化:

堆优化即为用堆将所有的距离进行维护,可降低查找当前最小距离的时间复杂度

由于类型的排序关键字为的值,所以距离值应该存在的位置上

应用场景:

用于稀疏图,时间复杂度为

2.算法:

3.算法:

  • 标题: 最短路
  • 作者: firstlight
  • 创建于 : 2023-09-28 21:50:00
  • 更新于 : 2025-01-22 22:41:04
  • 链接: https://blog.firstlightport.top/posts/zui-duan-lu/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论