1. The Single-Source Shortest Path Problem
-- Input: Directed graph G = (V , E), edge lengths ce for each e in E, source vertex s in V. [Can assume no parallel edges.]
-- Goal: For every destination v in V, compute the length (sum of edge costs) of a shortest s-v path.
2. Dijkstra's Algorithm
-- Good news: O(m log n) running time using heaps (n = number of vertices, m = number of edges)
-- Bad news:
(1) Not always correct with negative edge lengths
(2) Not very distributed (need information of the whole graph)
3. Negative Cycles
-- Question: How to define shortest path when G has a negative cycle?
-- Solution #1: Compute the shortest s-v path, with cycles allowed.
Problem: Undefined. [will keep traversing negative cycle]
-- Solution #2: Compute shortest cycle-free s-v path.
Problem: NP-hard (no polynomial algorithm, unless P=NP)
-- Solution #3: (For now) Assume input graph has no negative cycles.
Proposition: For every v, there is a shortest s-v path with n - 1 edges.
4. Optimal Substructure
-- Intuition: Exploit sequential nature of paths. Subpath of a shortest path should itself be shortest.
-- Issue: Not clear how to define "smaller" & "larger" subproblems.
-- Key idea: Artificially restrict the number of edges in a path.
Subproblem size <==> Number of permitted edges
5. Optimal Substructure Lemma
-- Lemma: Let G = (V , E) be a directed graph with edge lengths ce and source vertex s.
[G might or might not have a negative cycle]
-- For every v in V, i in {1 , 2 , ... }, let P = shortest s-v path with at most i edges. (Cycles are permitted.)
-- Case 1: If P has <= (i - 1) edges, it is a shortest s-v path with <= (i - 1) edges.
-- Case 2: If P has i edges with last hop (w , v), then P' is a shortest s-w path with (i - 1) edges.
6. The Recurrence
-- Notation: Let L(i , v) = minimum length of a s-v path with at most i edges.
-- With cycles allowed
-- Defined as +Infinity if no s-v paths with at most i edges
-- Recurrence: For every v in V, i in {1 , 2 , ... }
L(i , v) = min { L(i-1 , v) [Case 1] , min(u;v) in E {L(i-1 , w) + cwv} [Case 2] }
7. The Bellman-Ford Algorithm
-- Let A = 2-D array (indexed by i and v)
-- Base case: A[0 , s] = 0; A[0 , v] = +Infinity for all v <> s.
-- For i = 1, 2, ... , n - 1
For each v in V
A[i , v] = min { A[i - 1 , v] , min(w,v) in E {A[i - 1 , w] + cwv } }
-- If G has no negative cycle, then algorithm is correct [with final answers = A[n - 1 , v] ]
-- Total work is O( n Sum(v in V) { in-deg(v) } ) = O(mn)
n --> # iterations of outer loop (i.e. choices of i)
Sum(v in V) { in-deg(v) } --> work done in one iteration = m.
-- Stopping Early: Suppose for some j < n - 1, A[j , v] = A[j - 1, v] for all vertices v.
8. Checking for a Negative Cycle
-- G has no negative-cost cycle (that is reachable from s) <==> In the extended Bellman-Ford algorithm, A[n - 1 , v] = A[n , v] for all v in V.
-- Consequence: Can check for a negative cycle just by running Bellman-Ford for one extra iteration.
-- Proof.
==> Already proved in correctness of Bellman-Ford
<== Assume A[n - 1 , v] = A[n , v] for all v in V. (Assume also these are finite )
Let d(v) denote the common value of A[n - 1 , v] and A[n , v].
d(v) = A[n , v] = min { A[i - 1 , v] , min(w,v) in E { A[n - 1 , w] + cwv } }
Thus: d(v) <= d(w) + cwv for all edges (w , v) in E
Equivalently: d(v) - d(w) <= cwv
Consider an arbitrary cycle C. Sum (w , v) in C {cwv} >= Sum (w, v) in C { d(v) - d(w) } = 0
9. Space Optimization
-- Only need the A[i - 1 , v]'s to compute the A[i , v]'s ==> Only need O(n) to remember the current and last rounds of subproblems [only O(1) per destination!]
-- Concern: Without a filled-in table, how do we reconstruct the actual shortest paths?
-- Predecessor pointers : Compute a second table B, where B[i , v] = 2nd-to-last vertex on a shortest s --> v path with i edges (or NULL if no such paths exist)
-- Reconstruction: Tracing back predecessor pointers { the B[n - 1 , v]'s (= last hop of a shortest s-v path) -- from v to s yields a shortest s-v path.
10. Computing Predecessor Pointers
-- A[i , v] = min { (1) A[i - 1 , v] = (2) min(w,v) in E {A[i - 1 , w] + cwv } }
-- Base case: B[0 , v] =NULL for all v in V
-- To compute B[i , v] with i > 0:
Case 1: B[i , v] = B[i - 1 , v]
Case 2: B[i , v] = the vertex w achieving the minimum (i.e., the new last hop)
Correctness: Computation of A[i , v] is brute-force search through the (1+in-degree(v)) possible optimal solutions, B[i , v] is just caching the last hop of the winner.
To reconstruct a negative-cost cycle: Use depth-first search to check for a cycle of predecessor pointers after each round (must be a negative cost cycle).
11. From Bellman-Ford to Internet Routing
-- The Bellman-Ford algorithm is intuitively "distributed".
-- Switch from source-driven to destination driven [Just reverse all directions in the Bellman-Ford algorithm]. Every vertex v stores shortest-path distance from v to destination t and the first hop of a shortest path for all relevant destinations t.("Distance vector protocols")
-- Can't assume all A[i , v]'s get computed before all A[i - 1, v]'s. Switch from "pull-based" to "push-based": As soon as A[i , v] < A[i - 1 , v], v notifies all of its neighbors. Algorithm guaranteed to converge eventually. (Assuming no negative cycles) [Reason: Updates strictly decrease sum of shortest-path estimates]
-- Handling Failures: Each V maintains entire shortest path to t, not just the next hop.
Con: More space required.
Pro#1: More robust to failures. (Counting to Infitity)
Pro#2: Permits more sophisticated route selection (e.g., if you care about intermediate stops).
相关推荐
最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(CC++),希望对你能有所帮助!
本资料包聚焦于两种解决最短路径问题的算法:Bellman-Ford算法和SPFA(Shortest Path Faster Algorithm)。 **Bellman-Ford算法** Bellman-Ford算法由Richard Bellman在1958年提出,用于求解带负权边的图中源点到...
本篇将详细介绍两种解决最短路径问题的算法:Bellman-Ford算法和SPFA(Shortest Path Faster Algorithm)。 #### 2. Bellman-Ford算法详解 ##### 2.1 算法原理 Bellman-Ford算法能够处理含有负权重边的图,但前提是...
**贝尔曼-福特算法(Bellman-Ford Algorithm)详解** 在图论中,单源最短路径问题是一个经典的问题,即寻找从一个指定顶点(源点)到图中所有其他顶点的最短路径。贝尔曼-福特算法是解决这类问题的一种有效方法,...
此外,Bellman-Ford算法是Shortest Path Faster Algorithm (SPFA)的基础,SPFA是对Bellman-Ford算法的优化,虽然它的时间复杂度不如Dijkstra算法理想,但SPFA在某些特定情况下表现更优,尤其是在处理负权值边的问题...
这些提交的有用性非常有限,因为大多数真实的图问题都是稀疏的,并且大多数可以通过比 Dijkstra 早 4 或 5 年的 Bellman-Ford-Moore (BFM) 算法的变体更有效地解决。 更好的是,BFM 是健壮的,因为它可以处理负弧...
**贝尔曼-福特算法(Bellman-Ford Algorithm)** 贝尔曼-福特算法是一种在加权有向图中寻找从源节点到所有其他节点最短路径的算法。它是由理查德·贝尔曼在1958年提出的,适用于处理带有负权边的图,这是Dijkstra...
队列优化的Bellman-Ford最短路算法(SPFA,Shortest Path Faster Algorithm)是一种在图论中用于寻找有向图中单源最短路径的算法,它是在经典Bellman-Ford算法基础上进行优化得到的。Bellman-Ford算法本身能够处理...
多用户路由系统的分布式Bellman-Ford算法 一种。 开发环境的详细信息我使用eclipse和Java 1.6来开发我的代码。(JavaSE-1.6)不需要其他编码环境。 b。 有关如何运行代码的说明可以在计算机上的多个命令窗口上运行...
在C ++中实现Bellman-Ford算法。 编译步骤: a. I use Xcode to write my lab1 code in my MacBook Pro. Also in my zip file, there is a file named "LAB1.xcodeproj". b. Just directly open it and you ...
Destination-Sequenced Distance Vector is a table-driven routing scheme for ad hoc mobile networks based on the Bellman-Ford algorithm, Use of network simulation tool NS2, TCL coding.
Bellman-Ford algorithm Edmonds-Karp Maximal Flow Push–Relabel algorithm Huffman Coding Word segementation(CHN/GB18030) using HMM and viterbi algorithm. A* algorithm K-Means Knuth–Morris–Pratt ...
using Bellman-Ford algorithm and the efficacy of the same over Dijkstra’s algorithm is also demonstrated by a large set of simulation results. Simulation results also show that a gain in outage ...
贝尔曼-福特算法(Bellman-Ford Algorithm)同样可以处理负权重边,且能够检测出图中是否存在负权重循环。它的主要应用场景是在图中可能存在负权重边的情况下找到最短路径。 **算法步骤:** 1. 将起点到所有其他...
* Bellman-Ford Algorithm 十一、拥塞控制 *拥塞的概念 * 拥塞的原因 * 拥塞控制方法 * 通信量整形(令牌桶算法) 十二、局域网技术 * 局域网的拓扑结构 * 局域网的协议体系结构 * LLC 协议 * 集线器与交换机 * ...
OSPF使用的是SPF (Shortest Path First) 算法,也被称为迪杰斯特拉算法 (Dijkstra's algorithm)。SPF算法的工作原理是从源路由器出发,计算到达网络中各个目的地的最短路径。这些路径会被记录在一个路由表中,用于...
- **Bellman-Ford Algorithm**: 对于有权负边的图,Bellman-Ford算法可以找到最短路径,还能检测负权环,时间复杂度为O(V*E)。 - **Shortest Path Faster Algorithm**: 一种改进的Bellman-Ford算法,利用队列...
SPFA(Shortest Path Faster Algorithm)和Bellman-Ford算法是解决这类问题的两种有效方法,它们都能处理包含负权边的图,而Dijkstra算法则不适用于存在负权边的情况。 SPFA算法是由西南交通大学的段凡丁在1994年...
在使用 SPFA(Shortest Path Faster Algorithm,一种基于队列的 Bellman-Ford 变种)时,这个问题更加明显,因为 SPFA 是以点为中心进行松弛操作,没有源点可能导致某些边无法被正确松弛。 总的来说,差分约束系统...
**贝尔曼-福特算法(Bellman-Ford Algorithm)** 贝尔曼-福特算法是一种在图中寻找最短路径的算法,特别适用于存在负权边的情况。它由理查德·贝尔曼在1958年提出,是解决单源最短路径问题的一种方法。在有向图或无...