深圳公司网站建设哪家好,手机网站设计框架,网站认证打的钱怎么做分录,如何做网站支付链接本文意在探讨图中最短路径算法 Dijkstra、Floyd-Warshall、Bellman-Ford 的对比和细节
整体分为如下四部分
总结性的比较了 Dijkstra、Floyd-Warshall、Bellman-FordDijkstra 算法介绍Floyd-Warshall 算法介绍Bellman-Ford 算法介绍
其中1、2、3 算法介绍部分会比较简洁整体而言 Dijkstra 算法相对来说较难理解而 Floyd-Warshall、Bellman-Ford 通过伪代码可以快速理解其含义
建议可以先快速浏览 0然后看 2、3、1再阅读一次 0
0 最短路径中Dijkstra、Floyd-Warshall、Bellman-Ford 算法比较的 Cheat Sheet
比较维度DijkstraFloyd-WarshallBellman-Ford最佳用途寻找地图上点到点的最短路计算网络中所有点对的最短路路径规划/网络优化尤其是存在负权边时目标单源最短路径所有节点对的最短路径单源最短路径时间复杂度O(V^2) 或 O(E V log V)O(V^3)O(VE)空间复杂度O(V)O(V^2)O(V)负权边不支持仅正权边支持但不支持负权环支持且能检测负权环底层数据结构优先队列/堆二维数组数组是否适用于分布式否否是算法类型贪心算法动态规划动态规划实现难度中等简单简单更新策略单点更新全局更新单点更新路径重构直接通过前置节点通过中间节点递归构建直接通过前置节点
0.A 关于上面表格的问题 1
“是否适用于分布式” 是什么含义
0.A 问题 1 的回答
在这里“是否适用于分布式”指的是算法是否能够被有效地实施在一个分布式计算环境中也就是多个计算节点分别进行计算的情况。
对于分布式环境算法能否被分解成可以在网络中不同节点上独立运行的子过程是一个重要的考量。在这样的环境中节点通常只拥有局部的信息而不是整个网络的全局信息并且需要通过消息传递来协调解决方案。
例如Bellman-Ford算法可以被用在分布式系统中每个节点可以独立地运行算法的一部分并通过网络与其他节点交换信息。这个特性使其适用于如路由协议之类的分布式网络应用如RIPRouting Information Protocol。
相比之下Dijkstra算法和Floyd-Warshall算法通常在一个单一的计算实体上执行并需要有关全局网络的全部信息所以它们在标准形式下不适用于分布式环境。然而Dijkstra算法也有可能被修改为一个分布式版本如在OSPFOpen Shortest Path First路由协议中使用的那样。
0.B 关于上面表格的问题 2
Floyd-Warshall、Bellman-Ford 这两个算法是基于动态规划
我的知识储备中动态规划需要满足最优子结构和重叠子问题两个特征这两个算法是如何满足动态规划特性的
0.B 问题 2 的回答
Floyd-Warshall算法和Bellman-Ford算法确实是基于动态规划思想设计的下面解释它们是如何满足动态规划特性的
Floyd-Warshall算法 最优子结构Floyd-Warshall算法的最优子结构体现在计算任意两点i和j之间的最短路径时可以通过包含中间节点k的子路径来实现。如果已知从i到k和从k到j的最短路径那么可以通过它们来构建从i到j的最短路径。算法本质上是在尝试通过加入更多的中间节点来不断更新两点之间的最短路径。重叠子问题在计算节点对之间的最短路径时算法重复解决了许多相同的子问题。例如在计算从i到j的最短路径时需要用到从i到其他所有节点以及从所有节点到j的最短路径信息而这些信息在计算其他节点对之间的最短路径时会重复使用。 Bellman-Ford算法 最优子结构Bellman-Ford算法利用的最优子结构是指从源点到目标点的最短路径可以通过一系列的最短路径决策来构建。如果已知从源点到节点u的最短路径并且存在一条边从u到v那么只有当从源点经u到v的路径比已知的从源点到v的路径更短时才更新源点到v的距离。重叠子问题在更新节点间最短路径的过程中算法会在每次迭代中对所有边进行松弛操作。每次更新一个节点的最短路径估计时都可能用到其他节点的最短路径估计这些估计在算法的多个迭代中被重复计算和使用。
在这两个算法中动态规划的思想通过构建表格在Floyd-Warshall算法中是一个二维表格而在Bellman-Ford算法中通常是一维数组来保存子问题的解决方案并通过这些已解决的子问题来解决更大的问题。这些表格存储了算法的中间结果使得每个子问题只需要计算一次从而避免了重复计算。
1. Dijkstra 算法
算法概览在图中找到从源点到其他所有点的最短路径通过为每个顶点维护一个最短路径估计并逐渐更新这些估计直到找到最短路径。
伪代码
function Dijkstra(Graph, source):dist[source] ← 0 // 初始化源点到自己的距离为0for each vertex v in Graph: // 对图中每个顶点if v ≠ sourcedist[v] ← ∞ // 初始化源点到每个顶点的距离为无穷大prev[v] ← undefined // 前置节点初始化为未定义Q ← the set of all nodes in Graph // 将所有节点加入队列while Q is not empty: // 当队列非空时循环u ← vertex in Q with min dist[u] // 从Q中找出距离最小的顶点uremove u from Q // 从Q中移除顶点ufor each neighbor v of u: // 遍历u的所有邻居alt ← dist[u] length(u, v) // 计算经u到邻居v的距离if alt dist[v]: // 如果经u到v的距离更短dist[v] ← alt // 更新距离prev[v] ← u // 更新前置节点为ureturn dist, prev // 返回所有节点的最短距离以及路径在此伪代码中Graph 表示图source 表示源点dist 表示从源点到每个顶点的距离prev用来记录最短路径上的前置节点。Q 是一个优先队列用来找出当前未处理的最近的顶点。length(u, v) 是边 (u, v) 的权重。这个算法假设图中所有边的权重都是非负的。
2. Floyd-Warshall算法
算法概览核心思想是通过迭代过程考虑将所有其他顶点作为中间顶点来更新每对顶点之间的最短路径
伪代码
function FloydWarshall(W)n : length(W) // W is the graph represented as an adjacency matrixD : W // D is a distance matrix that will be updatedfor k from 1 to nfor i from 1 to nfor j from 1 to nif D[i][k] D[k][j] D[i][j] thenD[i][j] : D[i][k] D[k][j]return D在这里W 是一个邻接矩阵表示图中所有顶点之间的权重或距离。如果不存在直接的边那么W[i][j] 应该是一个非常大的数代表无穷。D 是 Floyd-Warshall 算法计算过程中的距离矩阵最后会变成所有顶点对之间最短路径的长度。在伪代码中n 是顶点的数目。
疑问
算法中的 i j k 循环顺序可以调整吗
解答
Floyd-Warshall 算法中的三个循环 (i, j, k) 的顺序是可以互换的但通常 k 循环是放在最外层的。在算法的迭代过程中k 循环代表的是允许作为中介点的顶点集合的逐步扩大。换句话说算法首先计算只允许使用顶点 1 作为中介的所有最短路径然后是顶点 1 和 2依此类推直到考虑所有顶点作为中介点。
将 k 循环放在最外层确保了在更新 D[i][j] 时考虑的所有中间顶点都是在之前的迭代中已经处理过的。如果 i 和 j 循环在 k 循环的外面算法就不能保证这一点可能会导致不正确的结果。
因此k 循环必须保持在最外层而 i 和 j 循环的顺序可以互换因为它们只是在独立地更新两点之间的最短距离。
3. Bellman-Ford 算法
算法概览通过对图中所有边进行重复松弛操作以计算图中单个源点到其他所有点的最短路径能够处理包含负权边的图。
伪代码
function BellmanFord(vertices, edges, source):// 初始化距离数组将源点到所有点的距离设为无穷大除了源点自身设为0distance : array of size |vertices|, fill with ∞ (infinity)distance[source] : 0// 循环|V|-1次V是顶点数量for i from 1 to |vertices|-1:// 对每条边进行一次松弛操作for each edge (u, v, w) in edges:if distance[u] w distance[v]:distance[v] : distance[u] w// 检测负权重循环// 再次对所有边进行检查如果还能找到更短的路径则存在负权重循环for each edge (u, v, w) in edges:if distance[u] w distance[v]:// 如果这里的条件为真则图中存在从源点可达的负权重循环return Graph contains a negative-weight cyclereturn distance疑问 1
for i from 1 to |vertices|-1:// 对每条边进行一次松弛操作for each edge (u, v, w) in edges:
...这里的 (u, v, w) 和外层循环 for i from 1 to |vertices|-1 有什么关系吗
u, v 需要是外层顶点循环中的一个吗
疑问 1 的回答
在贝尔曼-福特算法的伪代码中(u, v, w) 表示一条边其中 u 是起点v 是终点w 是这条边的权重。
这些边和外层顶点循环 for i from 1 to |vertices|-1 并没有直接的对应关系也就是说u 和 v 不需要是外层顶点循环中的特定顶点。
外层的循环 for i from 1 to |vertices|-1 的目的是重复尝试“松弛”操作足够多的次数确保算法能正确处理所有的最短路径即使这些路径可能通过多个顶点。在无负权重循环的情况下任何最短路径最多包含 |vertices|-1 条边。因此重复进行 |vertices|-1 次遍历所有边并尝试进行松弛操作足以保证算法找到所有可能的最短路径。
内层循环 for each edge (u, v, w) in edges 则是负责实际的松弛操作它会检查图中的每一条边无论这些边的起点和终点是什么。每次内层循环时算法会尝试更新从起点 u 到终点 v 的最短路径估计。
简而言之外层循环确保算法有足够的迭代次数来处理所有的最短路径而内层循环则是对具体的边进行操作两者各自独立共同配合完成算法的整个过程。
疑问 2
看起来 for each edge (u, v, w) in edges 中u、v 是可以对换的所以 distance[u] w distance[v] 为何不需要再判断 distance[v] w distance[u]
疑问 2 的回答
在 for each edge (u, v, w) in edges 这个循环中u 和 v 代表边的起点和终点它们并不是可以随意对换的。
有向图中 边是有方向的从 u 到 v 可能与从 v 到 u 的距离不同因为可能存在一条从 u 到 v 的边但不一定存在反方向的边即便存在其权重 w 也可能不同。算法中的 distance[u] w distance[v] 这个条件是在尝试进行松弛操作意思是如果你可以通过点 u 到达点 v并且这样做得到的路径比你目前记录的到点 v 的路径更短那么就更新到点 v 的最短路径距离。这是一个单向的检查。 无向图中 通常在输入的边集 edges 中每条无向边会被转换成两条有向边即一条从 u 到 v另一条从 v 到 u它们的权重是相同的。这样算法在遍历边的时候自然会检查每个方向的距离。因此不需要额外再判断 distance[v] w distance[u]因为算法会在遍历到边 (v, u, w) 时自然地处理这种情况其中 w 是从 v 到 u 的边的权重。在无向图中 w 和 w 是相同的在有向图中则可能不同。这保证了算法考虑了所有方向的边。
