【数据结构笔记24】单源最短路（迪克斯拉Dijkstra算法），多源最短路（弗洛伊德Floyd算法）

本文链接：https://blog.csdn.net/weixin_42815609/article/details/102565789

这篇笔记详细介绍了最短路径问题，包括无权图和有权图的单源最短路算法，特别是Dijkstra算法及其时间复杂度分析，并探讨了多源最短路问题的Floyd算法，适用于稠密图的情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

本次笔记内容：
7.1.1 概述
7.1.2 无权图的单源最短路
7.1.3 有权图的单源最短路
7.1.3-s 有权图的单源最短路示例
7.1.4 多源最短路算法

文章目录

最短路径问题

最短路径问题的抽象

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。

这条路径就是两点之间的最短路径（Shortest Path）；
第一个顶点为源点（Source）；
最后一个顶点为终点（Destination）。

问题分类

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径：
- （有向/无向）无权图
- （有向/无向）有权图
多源最短路径问题：求任意两顶点间的最短路径

无权图的单源最短路算法

按照递增（非递减）的顺序找出各个顶点的最短路。实际上就是广度优先搜索算法（BFS）。

在这里插入图片描述

void Unweighted(Vertex S)
{
   
    Enqueue(S, Q);
    while (!IsEmpty)
    {
   
        V = Dequeue(Q);
        for (V的每个邻接点W)
            if (dist[W] == -1)
            {
   
                dist[W] = dist[V] + 1;
                path[W] = V;
                Enqueue(W, Q);
            }
    }
}