1. Problem Definition:
Given an edge-weighted digraph, find the shortest path from s to t.
2. Different Vertices:
-- Source-sink: from one vertex to another.
-- Single source: from one vertex to every other.
-- All pairs: between all pairs of vertices.
3. Weighted directed edge: implementation in Java
public class DirectedEdge { private final int v, w; private final double weight; public DirectedEdge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; } public int from() { return v; } public int to() { return w; } public int weight() { return weight; } String toString() { return v + "->" + w; } }
4. Edge-weighted digraph: adjacency-lists implementation in Java
public class EdgeWeightedDigraph { private final int V; private final Bag<Edge>[] adj; public EdgeWeightedDigraph(int V) { this.V = V; adj = (Bag<DirectedEdge>[]) new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag<DirectedEdge>(); } public void addEdge(DirectedEdge e) { int v = e.from(); adj[v].add(e); } public Iterable<DirectedEdge> adj(int v) { return adj[v]; } }
5. Single-source shortest paths API
public class SP { SP(EdgeWeightedDigraph G, int s) {} //shortest paths from s in graph G double distTo(int v) {} //length of shortest path from s to v Iterable <DirectedEdge> {} //pathTo(int v) shortest path from s to v boolean hasPathTo(int v) {} //is there a path from s to v? }
6. Data structures for single-source shortest paths: Can represent the SPT with two vertex-indexed arrays:
-- distTo[v] is length of shortest path from s to v.
-- edgeTo[v] is last edge on shortest path from s to v.
7. Relax edge e = v→w.
-- distTo[v] is length of shortest known path from s to v.
-- distTo[w] is length of shortest known path from s to w.
-- edgeTo[w] is last edge on shortest known path from s to w.
-- If e = v→w gives shorter path to w through v, update both distTo[w] and edgeTo[w].
8. Shortest-paths optimality conditions:
distTo[] are the shortest path distances from s iff -->
-- For each vertex v, distTo[v] is the length of some path from s to v.
-- For each edge e = v→w, distTo[w] ≤ distTo[v] + e.weight().
Pf. ==> [necessary]
-- Suppose that distTo[w] > distTo[v] + e.weight() for some edge e = v→w.
-- Then, e gives a path from s to w (through v) of length less than distTo[w].
Pf. <== [sufficient]
-- Suppose that s = v0 → v1 → v2 → … → vk = w is a shortest path from s to w.
-- Then, distTo[w] = distTo[vk] ≤ distTo[vk-1] + ek.weight() ≤ distTo[vk-2] + ek-1.weight() + ek.weight()
≤ e1.weight() + e2.weight() + ... + ek.weight() (weight of shortest path)
-- Thus, distTo[w] is the weight of shortest path to w.
9. Generic shortest-paths algorithm:
-- Initialize distTo[s] = 0 and distTo[v] = ∞ for all other vertices.
-- Repeat until optimality conditions are satisfied:
-- Relax any edge.
Pf. of correctness
-- Throughout algorithm, distTo[v] is the length of a simple path from s to v (and edgeTo[v] is last edge on path).
-- Each successful relaxation decreases distTo[v] for some v.
-- The entry distTo[v] can decrease at most a finite number of times.
How to choose which edge to relax?
-- Dijkstra's algorithm (nonnegative weights).
-- Topological sort algorithm (no directed cycles).
-- Bellman-Ford algorithm (no negative cycles).
10. Dijkstra's algorithm:
-- Consider vertices in increasing order of distance from s
(non-tree vertex with the lowest distTo[] value).
-- Add vertex to tree and relax all edges pointing from that vertex.
Java implementation:
public class DijkstraSP { private DirectedEdge[] edgeTo; private double[] distTo; private IndexMinPQ<Double> pq; public DijkstraSP(EdgeWeightedDigraph G, int s) { edgeTo = new DirectedEdge[G.V()]; distTo = new double[G.V()]; pq = new IndexMinPQ<Double>(G.V()); for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; distTo[s] = 0.0; pq.insert(s, 0.0); while (!pq.isEmpty()) { int v = pq.delMin(); for (DirectedEdge e : G.adj(v)) relax(e); } } private void relax(DirectedEdge e) { int v = e.from(), w = e.to(); if (distTo[w] > distTo[v] + e.weight()) { distTo[w] = distTo[v] + e.weight(); edgeTo[w] = e; if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); else pq.insert (w, distTo[w]); } } }
Running Time:
11. Main distinction between Dijkstra's and Prims algorithm : Rule used to choose next vertex for the tree:
-- Prim’s: Closest vertex to the tree (via an undirected edge).
-- Dijkstra’s: Closest vertex to the source (via a directed path).
12. Shortest paths in edge-weighted DAGs:
-- Consider vertices in topological order.
-- Relax all edges pointing from that vertex.
Java Implementation:
public class AcyclicSP { private DirectedEdge[] edgeTo; private double[] distTo; public AcyclicSP(EdgeWeightedDigraph G, int s) { edgeTo = new DirectedEdge[G.V()]; distTo = new double[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; distTo[s] = 0.0; Topological topological = new Topological(G); for (int v : topological.order()) for (DirectedEdge e : G.adj(v)) relax(e); } }
13. Longest paths in edge-weighted DAGs:
-- Negate all weights.
-- Find shortest paths.
-- Negate weights in result.
Application: Parallel job scheduling. Given a set of jobs with durations and precedence constraints, schedule the jobs (by finding a start time for each) so as to achieve the minimum completion time, while respecting the constraints.
Solution: Critical path method -- create edge-weighted DAG:
-- Source and sink vertices.
-- Two vertices (begin and end) for each job.
-- Three edges for each job.
– begin to end (weighted by duration)
– source to begin (0 weight)
– end to sink (0 weight)
-- One edge for each precedence constraint (0 weight).
-- Use longest path from the source to schedule each job.
14. Bellman-Ford algorithm
-- Initialize distTo[s] = 0 and distTo[v] = ∞ for all other vertices.
-- Repeat V times:
- Relax each edge.
for (int i = 0; i < G.V(); i++) for (int v = 0; v < G.V(); v++) for (DirectedEdge e : G.adj(v)) relax(e);
Optimization: If distTo[v] does not change during pass i, no need to relax any edge pointing from v in pass i+1.
FIFO implementation: Maintain queue of vertices whose distTo[] changed. (Be careful to keep at most one copy of each vertex on queue.
Running Time :
Finding a negative cycle : If any vertex v is updated in phase V, there exists a negative cycle (and can trace back edgeTo[v] entries to find it).
15. Negative cycle application: arbitrage detection:
Given table of exchange rates, is there an arbitrage opportunity?
Currency exchange graph:
-- Vertex = currency.
-- Edge = transaction, with weight equal to exchange rate.
-- Find a directed cycle whose product of edge weights is > 1.
Model as a negative cycle detection problem by taking logs.
-- Let weight of edge v→w be - ln (exchange rate from currency v to w).
-- Multiplication turns to addition; > 1 turns to < 0.
-- Find a directed cycle whose sum of edge weights is < 0 (negative cycle).
16. Shortest paths summary
Dijkstra’s algorithm:
-- Nearly linear-time when weights are nonnegative.
-- Generalization encompasses DFS, BFS, and Prim.
Acyclic edge-weighted digraphs:
-- Arise in applications.
-- Faster than Dijkstra’s algorithm.
-- Negative weights are no problem.
Negative weights and negative cycles:
-- Arise in applications.
-- If no negative cycles, can find shortest paths via Bellman-Ford.
-- If negative cycles, can find one via Bellman-Ford.
相关推荐
K-Shortest Paths 算法相关论文
Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time MIKKEL THORUP 1999 Journal of the ACM 希望能够帮助到大家学习
这里仅给出了C++的实现方法,详细的数学证明请参见相关论文。特别要指出的是葡萄牙教授Martins对此算法有深入研究,发表了为数众多的相关论文,我这里采用的也是基于他早期提出的deletion algorithm。...
Single-source shortest paths. The following is the adjacency matrix, vertex A is the source. A B C D E A -1 3 B 3 2 2 C D 1 5 E -3 All-pairs shortest paths. The adjacency matrix is as ...
基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径...
Single-Source Shortest Paths 全英文版
最短路径算法实现 k-shortest-paths
最短路径算法实现 k-shortest-paths之c#源码
算法-最短路径计算最短路径的数量。 用Java编写。
最短路径Dijkstra算法的实现,以找到无向图中节点之间的最短(成本最低)路由。 并实现了A *搜索算法。 这个想法是通过将搜索指向t并使用欧几里得距离来改进Dijkstra的算法。 先决条件:Java要使两个.txt文件与...
mojo mojo_mojo编程示例之shortest_paths
1.6.2. 最短路Shortest paths 1.6.2.1. 单源最短路 Single-source shortest paths 1.6.2.1.1. 基本算法 Basic algorithms 1.6.2.1.1.1. Dijkstra 1.6.2.1.1.2. Bellman-Ford 1.6.2.1.1.2.1. Shortest path faster ...
1.6.2.1.2.2. 有向无环图上的最短路 Shortest paths in DAG 1.6.2.2. 所有顶点对间最短路 All-pairs shortest paths 1.6.2.2.1. 基本算法 Basic algorithms 1.6.2.2.1.1. Floyd-Warshall 1.6.2.2.1.2. Johnson 1.6.3...
Chapter 24 - Single-Source Shortest Paths Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix ...
Chapter 24 - Single-Source Shortest Paths Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix ...
24.2 Single-source shortest paths in directed acyclic graphs 655 24.3 Dijkstra’s algorithm 658 24.4 Difference constraints and shortest paths 664 24.5 Proofs of shortest-paths properties 671 25 All-...
Chapter 24 - Single-Source Shortest Paths Chapter 25 - All-Pairs Shortest Paths Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix ...
3 Weak Visibility and Shortest Paths 46 3.1 Problems and Results 46 3.2 Characterizing Weak Visibility 51 3.3 Computing Weak Visibility in Simple Polygons 58 3.3.1 Scanning the Boundary: O(n log n) ...