Dijkstra与Floyd算法解决最短路径问题详解

"本章小结涵盖了图论中的重要概念，特别是最短路径问题的解决方案，包括Dijkstra算法和Floyd算法。" 在图论中，图被用来表示对象之间的关系，可以分为有向图（边有方向）和无向图（边无方向）。完全图是指图中任意两个不同的顶点间都有唯一的边相连。子图则是原图的一部分，包含原图的部分顶点和这些顶点间的边。连通图是指图中任意两个顶点之间都存在路径。度是指一个顶点的邻接边数量，分为入度（进入顶点的边数）和出度（离开顶点的边数）。简单回路和环是指不含重复顶点的路径和包含至少一个顶点重复的环形路径。 图的存储结构主要包括邻接矩阵和邻接表。邻接矩阵用二维数组表示，如果图是有向的，矩阵是对称的；无向图则是对称矩阵，矩阵元素表示对应顶点间是否有边。邻接表则以链表形式存储每个顶点的邻接点，节省空间，适用于稀疏图。 在图的运算中，创建图涉及初始化顶点和边；输出图是将图的结构可视化；深度优先遍历和广度优先遍历是图的搜索策略，分别以深度和广度优先的方式遍历所有顶点。 最短路径问题在图论中至关重要。对于无权图，最短路径是指经过最少边的路径；而在带权图中，最短路径是指边权重之和最小的路径。Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻提出的，用于解决单源最短路径问题。其核心思想是逐步扩展已知最短路径的顶点集合，确保每次扩展后所有已知路径都是最短的。算法初始时，源点距离自身为0，其他顶点距离无穷大。然后通过不断更新未访问顶点的距离，找到下一个距离最小的顶点并将其加入已访问集合，直到所有顶点都被访问。 Dijkstra算法的具体步骤如下： 1. 初始化：设置S={v0}，dist[i]表示v0到vi的最短路径距离，所有dist[i]根据边的权重设置。 2. 选择未访问顶点u，使得dist[u]最小。 3. 将u加入S，更新所有未加入S的顶点Vi的最短路径：如果通过u到达Vi的路径比当前dist[vi]更短，则更新dist[vi]。 4. 重复步骤2和3，直到所有顶点都在S中。 Floyd算法，又称Floyd-Warshall算法，用于解决所有顶点对的最短路径问题，它通过迭代逐个考虑中间节点来更新最短路径信息，适用于所有可能存在的负权边的情况。不过，这里主要讨论的是Dijkstra算法及其在带权有向图中最短路径的求解。