Dijkstra与Floyd算法详解：Matlab实现与时间复杂度比较

本文档主要探讨了两种经典的图论算法在Matlab中的实现：Dijkstra算法和Floyd-Warshall算法。Dijkstra算法用于寻找有向或无向图中两点之间的最短路径，其核心思想是贪心策略，通过逐步更新节点间的最短路径长度。在Matlab函数`Graph::Dijkstra`中： 1. 初始化：将所有节点到起点的距离设为边的权重，起点的距离设为0，标记起点已处理。 2. 主循环：遍历未处理节点，查找当前最小距离的节点，并更新与其相邻节点的距离，同时记录前趋节点。 3. 当找到无限大（infinity）表示没有更短路径时，算法结束。 Floyd-Warshall算法则更进一步，它计算图中任意两个节点之间的所有最短路径，适用于稠密图。在`Graph::Floyd_Warshall`函数中，执行以下步骤： 1. 初始化：将所有节点对的距离设置为边的权重，所有节点到自身的距离设为0，前趋节点为自身。 2. 遍历所有节点作为中间节点，更新每对节点之间的最短路径，如果发现经过某个中间节点的路径比当前直接路径短，则更新路径长度并记录前趋节点。 3. 不处理孤立节点，确保算法只考虑相连的节点对。 这两个算法的时间复杂度分别为： - Dijkstra算法：时间复杂度为O(NV^2)，其中N为节点数，V为边数。 - Floyd-Warshall算法：时间复杂度为O(NV * |E| + NV^2)，|E|为边的数量，当|E|远大于V^2时，Floyd-Warshall可能更有效。 在实现时，需要注意以下几点： - 边的权重不能为负值，因为负权重可能导致算法无法正确工作。 - 当两个节点之间不存在边时，矩阵中的对应元素应设置为无穷大（infinity），以避免错误的路径搜索。 - 为了避免重复计算，可以使用布尔向量M来跟踪节点是否已经被处理过。 本文档提供了使用Matlab实现Dijkstra和Floyd-Warshall算法的具体代码，并强调了算法的基本原理、适用场景以及在Matlab环境中的注意事项，这对于理解和应用这两种基础图算法非常有帮助。