Path & Reachability (Cont)
COMP9312_22T2
– Reachability
Copyright By PowCoder代写 加微信 powcoder
Transitive closure
Optimal Tree cover Two-Hop labelling
– Shortest Path
Dijkstra’s algorithm
A* algorithm Floyd-Warshall algorithm
Shortest Distance/Path
Shortest path
1. Single-source shortest path problem (finding the shortest paths between a given vertex v and all other vertices in the graph)
– Dijkstra’s algorithm (very similar to Prim’s algorithm; assumes all weights are positive) – If we only want to find the shortest path to one given goal node, A* algorithm
2. All pair shortest path (find the pairwise shortest distances as well as the corresponding paths)
– Floyd-Warshall algorithm
BFS-based shortest path
Find the shortest path from vertex u to v.
A naive BFS-based approach:
(1) conduct a BFS from the source vertex u
(2) for each visited vertex, record its parent in the searching tree (3) when the target vertex v is visited, terminate BFS.
(4) recursively return the path from u to v.
Find the shortest path from A to D by performing a breadth-first traversal
Pop A and push B, C, E.
Parents of visited vertices:
Pop B and push D into the queue.
Since D is found, terminate BFS! Based on the recorded parent vertices, one path is A->B->D.
Parents of visited vertices:
BFS-based shortest path
1. Can we guarantee that this path is the shortest? If so, is it the only shortest path?
Yes, we can. No, in the above example, A->C->D is another path with
2. Time complexity? Space complexity?
The time complexity is O(m) which is the same with BFS. Slightly faster in practice because of the early termination. The space complexity is O(n) since we need to record the parent vertex of each visited vertex.
3. Can we use the above algorithm to solve the single-source shortest path problem and the all pairs shortest path problem?
Dijkstra’s Algorithm
Motivation
Single-source shortest path problem (finding the shortest paths between a given vertex v and all other vertices in the graph)
Suppose you are at vertex A
• Youareawareofallverticesadjacenttoit
• Thisinformationiseitherinanadjacencylistoradjacencymatrix
Q: Is 5 the shortest distance to B via the edge (A, B)?
Q: Are you guaranteed that the shortest path to C is (A, C), or that (A, D) is the shortest path to vertex D?
Motivation
Let’s see where we can go from B
By some simple arithmetic, we can determine that • Thereisapath(A,B,E)oflength5+7=12
• Thereisapath(A,B,F)oflength5+3=8
Motivation
Is (A, B, F) is the shortest path from vertex A to F? • Why or why not?
Yes, because 5+3<9, 5+3<15, and 3 is the smallest weight from B.
Motivation
Are we guaranteed that any other path we are currently aware of is also going to be the shortest path?
Motivation
Okay, let’s visit vertex F
• We know the shortest path is (A, B, F) and it’s of length 8
Motivation
There are three edges exiting vertex F, so we have paths:
• (A,B,F,E)oflength8+6=14 • (A,B,F,G)oflength8+4=12 • (A,B,F,C)oflength8+2=10
Motivation
By observation:
• Thepath(A,B,F,E)islongerthan(A,B,E)
• Thepath(A,B,F,C)isshorterthanthepath(A,C)
Motivation
At this point, we’ve discovered the shortest paths to: • Vertex B: (A, B) of length 5
• Vertex F: (A, B, F) of length 8
Motivation
At this point, we have the shortest distances to B and F
• Which remaining vertex are we currently guaranteed to have the shortest distance to?
D. Because D is the unvisited vertex which has the shortest distance right now.
Dijkstra’s algorithm
• Like Prim’s algorithm, we initially don’t know the distance to any vertex except the initial vertex. Thus, we require an array of distances, all initialized to infinity except for the source vertex, which is initialized to 0.
• Each time we visit a vertex, we will examine all adjacent vertices. We need to track visited vertices—a Boolean table of size |V|
How to track the shortest path to each vertex?
Do I have to store (A, B, F) as the shortest path to vertex F?
We really only have to record that the shortest path to vertex F came from vertex B We would then determine that the shortest path to vertex B came from vertex A Thus, we need an array of previous vertices, all initialized to null
Dijkstra’s algorithm
We will iterate |V| times:
• Find that unvisited vertex v that has a minimum distance to it. Mark it
as having been visited.
• Consider every adjacent vertex w that is unvisited:
- Is the distance to v plus the weight of the edge (v, w) less than our currently known shortest distance to w. If so, update the shortest distance to w and record v as the previous pointer.
• Continue iterating until all vertices are visited or all remaining vertices have a distance to them of infinity.
Consider the game of Risk from • A game of world domination
• The world is divided into 42 connected regions
• The regions are vertices and edges indicate adjacent regions
We’ll focus on Asia. Here is our abstract representation.
Let us give a weight to each of the edges.
Find the shortest distance from Kamchatka (K) to every other region
http://thunderbird37.com/tag/paker-brothers/
We set up our table as follows.
We visit vertex K
Vertex K has four neighbors: H, I, J and L
We have now found at least one path to each of these vertices
We’re finished with vertex K.
To which vertex are we now guaranteed we have the shortest path?
We visit vertex H: the shortest path is (K, H) of length 8 Vertex H has four unvisited neighbors: E, G, I, L
Consider these paths:
• (K, H, E) of length 8 + 6 = 14
• (K, H, I) of length 8 + 2 = 10
Which of these are shorter than any known path?
(K, H, G) of length 8 + 11 = 19 (K, H, L) of length 8 + 9 = 17
We already have a shorter path (K, L), but we update the other three
We are finished with vertex H. Which vertex do we visit next?
The path (K, H, I) is the shortest path from K to I of length 10 Vertex I has two unvisited neighbors: G and J
Consider these paths:
(K, H, I, G) of length 10 + 3 = 13 (K, H, I, J) of length 10 + 18 = 28
We have discovered a shorter path to vertex G, but (K, J) is still the shortest known path to vertex J
Which vertex can we visit next?
The path (K, H, I, G) is the shortest path from K to G of length 13. Vertex G has three unvisited neighbors: E, F and J.
Consider these paths:
• (K,H,I,G,E)oflength13+15=28 (K,H,I,G,F)oflength13+4=17 • (K,H,I,G,J)oflength13+19=32
• Which do we update?
We have now found a path to vertex F
Where do we visit next?
The path (K, H, E) is the shortest path from K to E of length 14. Vertex E has four unvisited neighbors: B, C, D and F.
The path (K, H, E) is the shortest path from K to E of length 14 Vertex E has four unvisited neighbors: B, C, D and F
Consider these paths:
• (K,H,E,B)oflength14+5=19 • (K,H,E,D)oflength14+10=24
• Which do we update?
(K,H,E,C)oflength14+1=15 (K,H,E,F)oflength14+22=36
We’ve discovered paths to vertices B, C, D
Which vertex is next?
We’ve found that the path (K, H, E, C) of length 15 is the shortest path from K to C.
Vertex C has one unvisited neighbor, B.
The path (K, H, E, C, B) is of length 15 + 7 = 22.
We have already discovered a shorter path through vertex E.
Where to next?
We now know that (K, L) is the shortest path between these two points.
Vertex L has no unvisited neighbors.
Where to next?
Does it matter if we visit vertex F first or vertex J first?
Let’s visit vertex F first.
It has one unvisited neighbor, vertex D
The path (K, H, I, G, F, D) is of length 17 + 14 = 31. This is longer than the path we’ve already discovered.
Now we visit vertex J.
It has no unvisited neighbors
Next we visit vertex B, which has two unvisited neighbors:
• (K,H,E,B,A)oflength19+20=39 (K,H,E,B,D)oflength19+13=32 • We update the path length to A
Next we visit vertex D
The path (K, H, E, D, A) is of length 24 + 21 = 45 We don’t update A.
Finally, we visit vertex A.
It has no unvisited neighbors and there are no unvisited vertices left. We are done.
Thus, we have found the shortest path from vertex K to each of the other vertices
Using the previous pointers, we can reconstruct the paths
Note that this table defines a rooted parental tree.
The source vertex K is at the root.
The previous pointer is the parent of the vertex in the tree
Comments on Dijkstra’s algorithm
Questions:
• What if at some point, all unvisited vertices have a distance ∞?
• This means that the graph is unconnected
• We have found the shortest paths to all vertices in the connected subgraph containing the source vertex
• What if we just want to find the shortest path between vertices vj and vk? • Apply the same algorithm, but stop when we are visiting vertex vk
• Does the algorithm change if we have a directed graph? • No
Implementation and analysis
• The initialization requires O(|V|) memory and run time
We iterate |V| – 1 times, each time finding the unvisited closest vertex • Iterating through the table requires is O(|V|) time
• Each time we find a vertex, we must check all of its neighbors
• With an adjacency matrix, the run time is O(|V|(|V| + |V|)) = O(|V|2)
• With an adjacency list, the run time is O(|V|2 + |E|) = O(|V|2) as |E| = O(|V|2) Can we do better?
Recall, we only need the vertex with the shortest distance next. We can use min-heap similar as the Prim’s algorithm.
Min-heap-based optimization
a min heap – TheminheaprequiresO(|V|)memorywhichcontainstheshortestdistanceofallthe
vertices from the source vertex
We iterate |V| times, each time finding the unvisited closest vertex to the source
– ObtaintheshortestdistancefromtheminheapO(1),maintaintheheapO(log(|V|))
– TheworkrequiredforthisisO(|V|log(|V|)) Is this all the work that is necessary?
– Recallthatfortheclosestvertexinaniteration,wetrytoupdatethedistanceofallits neighbors, thus there are O(|E|) updates in total and each update in the heap requires O(log(|V|)).
– Thus,theworkrequiredforthisisO(|E|log(|V|))
Thus, the total run time is O(|V| log(|V|) + |E| log(|V|)) = O(|E| log(|V|))
The initialization requires O(|V|) memory and run time
Quick Exercise
Given the graph below, apply Dijkstra’s Algorithm to find the shortest paths from S.
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Quick Exercise
Summary for Dijkstra’s algorithm
Single source shortest distance/path for weighted graphs Compute shortest distance/path for a pair of vertices in practice:
Bidirectional search
Motivation: Triangle Inequality
Starting fro
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com