1. Problem Denition
-- Input: Directed graph G = (V , E) with edge costs ce for each edge e in E, [No distinguished source vertex.]
-- Goal: Either
(A) Compute the length of a shortest u --> v path for all pairs of vertices u, v in V
(B) Correctly report that G contains a negative cycle.
2. Invocations of a single-source shortest-path subroutine
-- n Dijkstra = O(nm log n) =
-- O(n^2 log n) if m = O(n)
-- O(n^3 log n) if m = O(n^2)
-- n Bellman-Ford = O(n^2m) =
-- O(n^3) if m = O(n)
-- O(n^4) if m = O(n^2)
3. Floyd-Warshall algorithm
-- Running time : O(n^3) algorithm for APSP. Works even with graphs with negative edge lengths.
-- At least as good as n Bellman-Fords, better in dense graphs.
-- In graphs with nonnegative edge costs, competitive with n Dijkstra's in dense graphs.
4. Optimal Substructure
-- Recall: Can be tricky to define ordering on subproblems in graph problems.
-- Key idea: Order the vertices V = {1, 2, ... , n} arbitrarily. Let V(k) = {1, 2, ... , k}.
-- Lemma: Suppose G has no negative cycle. Fix source i in V, destination j in V, and k in {1, 2, ... , n}. Let P = shortest (cycle-free) i -j path with all internal nodes in V(k).
-- Optimal substructure lemma:
Suppose G has no negative cost cycle. Let P be a shortest (cycle-free) i -j path with all internal
nodes in V(k). Then:
Case 1: If k not internal to P, then P is a shortest (cycle-free) i -j path with all internal vertices in V(k-1).
Case 2: If k is internal to P, then: P1 = shortest (cycle-free) i -k path with all internal nodes in
V(k-1) and P2 = shortest (cycle-free) k-j path with all internal nodes in V(k-1)
5. The Floyd-Warshall Algorithm :
-- Let A = 3-D array (indexed by i , j , k)
-- Base cases: For all i , j in V:
A[i , j , 0] = 0 if i = j ; cij if (i , j) in E ; +Infinity if i <> j and (i , j) not in E
For k = 1 to n
For i = 1 to n
For j = 1 to n
A[i , j , k] = min { A[i , j , k - 1] [Case 1] , A[i , k , k - 1] + A[k , j , k - 1] [Case 2]
-- Correctness: From optimal substructure + induction, as usual.
-- Running time: O(1) per subproblem, O(n^3) overall.
6. Handling Negative Cycle :
-- Will have A[i , i , n] < 0 for at least one i in V at end of algorithm if the input graph has negative cost cycle.
-- Reconstruction : Have Floyd-Warshall compute B[i , j ] = max label of an internal node on a shortest i -j path for all i , j in V. ( Reset B[i , j ] = k if 2nd case of recurrence used to compute
A[i , j , k] ) ==> Can use the B[i , j ]'s to recursively reconstruct shortest paths.
7. Johnson's algorithm
-- Reduces APSP to :
-- 1 invocation of Bellman-Ford (O(mn) )
-- n invocations of Dijkstra (O(nm log n))
-- Running time: O(mn) + O(mn log n) = O(mn log n) (As good as with nonnegative edge lengths)
8. Reweighting :
-- G = (V , E) is a directed graph with general edge lengths ce. Fix a real number pv for each vertex v in V.
-- For every edge e = (u , v) of G, ce' = ce + pu - pv , If the s-t path P has length L with the original edge lengths {ce}, P's length with the new edge length {ce'} is :
Sum(e in P) { ce' } = Sum( e = (u,v) in P ) { ce + pu - pv } = (Sum ( e in P ) {ce} ) + ps - pt
-- Summary: Reweighting using vertex weights {pv} adds the same amount (namely, ps - pt ) to every s-t path. Reweighting always leaves the shortest path unchanged.
-- After reweighting by some {pv}, all edge lengths become nonnegative!
9. Johnson's Algorithm:
-- Input: Directed graph G = (V , E), general edge lengths ce .
-- (1) Form G' by adding a new vertex s and a new edge (s , v) with length 0 for each v in G.
-- (2) Run Bellman-Ford on G' with source vertex s. [If B-F detects a negative-cost cycle in G' (which must lie in G), halt + report this.]
-- (3) For each v in G, define pv = length of a shortest s --> v path in G'.
For each edge e = (u , v) in G, define ce' = ce + pu - pv.
-- (4) For each vertex u of G: Run Dijkstra's algorithm in G, with edge lengths {ce'}, with source vertex u, to compute the shortest-path distance d'(u , v) for each v in G.
-- (5) For each pair u , v in G, return the shortest-path distance d(u , v) := d'(u , v) - pu + pv
-- Runing time : O(nm log n)
-- Step (1) , form G' --> O(n)
-- Step (2) , run BF --> O(mn)
-- Step (3), form c' --> O(m)
-- Step (4), n Dijkstra --> O(nm log n)
-- Step (5), O(1) work per u-v pair --> O(n2)
10. Correctness of Johnson's Algorithm
-- Claim: For every edge e = (u , v) of G, the reweighted length ce' = ce + pu - pv is nonnegative.
-- Proof: Fix an edge (u , v). By construction,
pu = length of a shortest s-u path in G'
pv = length of a shortest s-v path in G'
Let P = a shortest s-u path in G' (with length pu --> exists, by construction of G')
==> P + (u , v) = an s-v path with length pu + cuv
==> Shortest s-v path only shorter, so pv <= pu + cuv
==> c'uv = cuv + pu - pv >= 0.
相关推荐
在图论中,All-Pairs-Shortest-Paths(APSP)问题是一个经典的问题,它旨在找出给定加权无向图或有向图中所有节点对之间的最短路径。这个问题在许多领域都有应用,包括网络设计、交通规划、社交网络分析等。Floyd-...
All-pairs shortest paths. The adjacency matrix is as same as that of problem 3.(Use Floyd or Johnson’s algorithm) Practice 4 Date: Monday, May 8th, 2013 We highly encourage being environment ...
cd spark-all-pairs-shortest-path / sbt软件包 在集群上运行Spark的命令 scp -i keyname.pem target / scala-2.10 / all-pairs-shortest-path_2.10-1.0.jar :〜/ ssh -i keyname.pem 现在将罐子放入hdfs ./...
auto-pairs是vim的一个极小的插件。它对于用vim来编写程序,提供了极大的便。我ubuntu16中,用vim编写c和c++程序,安装了此插件,极大地方便了代码的输入。 二、功能介绍: 它可以自动完成大括号、小括号、中括号、...
Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming ...
Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming ...
Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming ...
Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming ...
Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming ...
安装手动的将plugin/auto-pairs.vim复制到~/.vim/plugin git clone git://github.com/jiangmiao/auto-pairs.git ~/.vim/bundle/auto-pairsPlugin 'jiangmiao/auto-pairs'特征成对插入 input: [output: [|]成对删除 ...
"quora-question-pairs"竞赛提供了大量问题对,目的是通过算法来确定哪些问题是重复的。这个任务涉及到自然语言处理(NLP)的核心技术,特别是文本相似度计算。这里我们将深入探讨这个竞赛中直接可用的特征结果,...
该函数计算动态网络中所有节点对之间的最短动态路径长度,该长度在论文“Understanding and Modeling the Small-World Phenomenon in Dynamic Networks - AD. Nguyen et al - MSWIM 2012”中定义。...
Chapter 25: All-Pairs Shortest Paths Lecture Notes 25-1 Solutions 25-9 Chapter 26: Maximum Flow Lecture Notes 26-1 Solutions 26-12 Chapter 27: Multithreaded Algorithms Solutions 27-1 Index I-1
《All-pairs GPU》是与计算生物学和生物信息学领域相关的开源软件项目,旨在利用图形处理单元(GPU)的强大计算能力来解决所有对问题。在现代科学数据分析中,尤其是在生物领域,经常需要处理大量数据,并进行复杂的...
keras-quora-question-pairs, 一个Keras模型,解决了Quora问题对的二 keras-quora-question-pairs一个Keras模型,它解决了Quora的问题对 [1] 。模型实现Keras模型体系结构如下所示: model architecture ...
js js_leetcode题解之24-swap-nodes-in-pairs.js
c语言入门 C语言_leetcode题解之24-swap-nodes-in-pairs.c
功能是: xah-replace-pairs-region Xah替换成对的字符串xah-replace-regexp-pairs-region xah-replace-regexp-pairs-in-string xah-replace-pairs-region-recursive xah-replace-pairs-in-string-recursive 详情见...
ALLSPATH - 解决所有对最短路径问题 对于图形中的所有节点,快速返回沿图形边缘的最短节点到节点的距离。 用法:B = allspath(A) A = 节点之间的输入距离矩阵 B = 所有节点之间的最短路径距离矩阵 ...