程序代写代做代考 algorithm data structure C graph COMP90038 – Algorithms and Complexity Lecture 20

COMP90038 – Algorithms and Complexity Lecture 20
COMP90038 Algorithms and Complexity
Lecture 20: Prim and Dijkstra
(with thanks to Harald Søndergaard & Michael Kirley)
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Warshall’s Algorithm
• Assume the nodes of graph G are numbered from 1 to n.
• Ask the question: Is there a path from node 𝑖 to node 𝑗 using only nodes that are no
larger than some k as “stepping stones”?
• Such a path either uses node k as a stepping stone, or it doesn’t.
• So an answer is: There is such a path if and only if we can step from 𝑖 to 𝑗 using only nodes ≤ 𝑘 − 1, or
step from 𝑖 to k using only nodes ≤ 𝑘 − 1, and then step from k to j using only nodes ≤ 𝑘 − 1.

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Warshall’s Algorithm
• This leads to a better version of Warshall’s algorithm:
• If each row in the matrix is represented as a bit-string, the innermost for loop (and 𝑗) can be gotten rid of–instead of iterating, just apply the “bitwise or” of row k to row i.

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Warshall’s Algorithm
1234567
1 0100100
0010000 0000011 0010000 0100010 0001001 0001000
2 3 4 5 6 7

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Warshall’s Algorithm
1234567
1 0111111
0011011 0011011 0011011 0111011 0011011 0011011
2 3 4 5 6 7

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Floyd’s Algorithm
• We can use the same problem decomposition as we used to derive Warshall’s algorithm. Again assume nodes are numbered 1 to 𝑛.
• This time ask the question: What is the shortest path from node 𝑖 to node 𝑗 using only nodes ≤ 𝑘 as “stepping stones”?
• We either use node 𝑘 as a stepping stone, or we avoid it. So again, we can step from 𝑖 to 𝑗 using only nodes ≤ 𝑘 − 1, or
step from 𝑖 to k using only nodes ≤ 𝑘 − 1, and then step from k to j using only nodes ≤ 𝑘 − 1.

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Floyd’s Algorithm
• If 𝐺’s weight matrix is 𝑊 then we can express the recurrence relation for minimal distances as follows:
𝐷# =𝑊𝑖,𝑗 !”
𝐷$ = min 𝐷$%&, 𝐷$%& + 𝐷$%& !” !” !$ $”
• And then the algorithm follows easily:

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Floyd’s Algorithm
12345 12345
10111∞ 101112 210∞11 ⇒210211 31∞01∞ 312012 411101 411101 5∞1∞10 521210

COMP90038 – Algorithms and Complexity
Lecture 20
Review from Lecture 19: Floyd’s Algorithm
1 2 3 4 5 6 7
1234567
09∞∞7∞∞
905∞4∞∞ ∞506∞26 ∞∞60∞76
74∞∞04∞ ∞∞27407 ∞∞66∞70
1234567
0 9 13 18 7 11 18
9 0 5 11 4 7 11 13 5 0 6 6 2 6 18 11 6 0 11 7 6
7 4 6 11 0 4 11 11 7 2 7 4 0 7 18 11 6 6 11 7 0
1 2 3 4 5 6 7

COMP90038 – Algorithms and Complexity Lecture 20
Greedy Algorithms
• A natural strategy to problem solving is to make decision based on what is the locally best choice.
• Suppose we have coin denominations 25, 10, 5 and 1, and we want to make up 30 cents using the smallest number of coins.
• In general, we will want to use as many 25-cent pieces as we can, then do the same for 10-cent pieces, and so on, until we have reached 30 cents. (In this case we use 25+5 cents.)
• This greedy strategy will work for the given denominations, but not for, say 25, 10, 1. (compare 25+1+1+1+1+1 with 10+10+10).

COMP90038 – Algorithms and Complexity Lecture 20
Greedy Algorithms
• In general we cannot expect locally best choices to yield globally best outcomes.
• However, there are some well-known algorithms that rely on the greedy approach,
being both correct and fast.
• In other cases, for hard problems, a greedy algorithm can sometimes serve as an acceptable approximation algorithm (we will discuss approximation algorithms in Week 12).
• Here we shall look at
– Prim’s algorithm for finding minimum spanning trees – Dijkstra’s algorithm for single-source shortest paths.

COMP90038 – Algorithms and Complexity Lecture 20
Spanning Trees
• Recall that a tree is a connected graph with no cycle.
• A spanning tree of a graph 𝑉, 𝐸 is a tree 𝑉, 𝐸′ with E′ ⊆ 𝐸.
• The graph has eight different spanning trees:

COMP90038 – Algorithms and Complexity
Lecture 20
Minimum Spanning Trees of Weighted Graphs
• In applications where the edges correspond to distances, or cost, some spanning trees will be more desirable than others.
• Suppose we have a set of ‘stations’ to connect in a network, and also some possible connections, together with the cost of each connection.
• Then we have a weighted graph problem, of finding a spanning tree with the smallest possible cost.

COMP90038 – Algorithms and Complexity
Lecture 20
Minimum Spanning Trees
• Given a weighted graph, a sub-graph which is a tree with minimal weight is a minimum spanning tree for the graph.

COMP90038 – Algorithms and Complexity
Lecture 20
Minimum Spanning Trees: Prim’s Algorithm
• Prim’s algorithm is an example of a greedy algorithm.
• It constructs a sequence of subtrees 𝑇, each adding a node together with an edge to a node in the previous subtree. In each step it picks a closest node from outside the tree and adds that. A sketch:

COMP90038 – Algorithms and Complexity Lecture 20
Prim’s Algorithm
• Note that in each iteration, the tree grows by one edge.
• Or, we can say that the tree grows to include the node from outside that has the
smallest cost.
• But how to find the minimum-weight edge (𝑣, 𝑢)?
• A standard way to do this is to organise the nodes that are not yet included in the spanning tree 𝑇 as a priority queue, organised in a min-heap by edge cost.
• The information about which nodes are connected in 𝑇 can be captured by an array 𝑝𝑟𝑒𝑣 of nodes, indexed by 𝑉. Namely, when (𝑣, 𝑢) is included, this is captured by setting prev 𝑢 = 𝑣.

COMP90038 – Algorithms and Complexity Lecture 20
Prim’s Algorithm

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• On the first loop, we only create the table.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• Then we pick the first node as the initial one.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We take the first node out of the queue & update the costs.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
5
6
4
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We eject the node with the lowest cost & update the queue.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
5
6
4
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
2
2
∞
4
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑛𝑖𝑙
𝑑

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We eject the next node based on alphabetical order.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
5
6
4
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
2
2
∞
4
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏
𝑐𝑜𝑠𝑡
1
∞
4
𝑝𝑟𝑒𝑣
𝑏
𝑛𝑖𝑙
𝑑

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We now update (𝑓).
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
5
6
4
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
2
2
∞
4
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏
𝑐𝑜𝑠𝑡
1
∞
4
𝑝𝑟𝑒𝑣
𝑏
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏,𝑐
𝑐𝑜𝑠𝑡
5
3
𝑝𝑟𝑒𝑣
𝑐
𝑐

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We have reached the last choice.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
5
6
4
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
2
2
∞
4
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏
𝑐𝑜𝑠𝑡
1
∞
4
𝑝𝑟𝑒𝑣
𝑏
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏,𝑐
𝑐𝑜𝑠𝑡
5
3
𝑝𝑟𝑒𝑣
𝑐
𝑐
𝑎,𝑑,𝑏,𝑐,𝑓
𝑐𝑜𝑠𝑡
4
𝑝𝑟𝑒𝑣
𝑓

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• The resulting tree is 𝑎,𝑑,𝑏,𝑐,𝑓,𝑒 .
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
5
6
4
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
2
2
∞
4
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏
𝑐𝑜𝑠𝑡
1
∞
4
𝑝𝑟𝑒𝑣
𝑏
𝑛𝑖𝑙
𝑑
𝑎,𝑑,𝑏,𝑐
𝑐𝑜𝑠𝑡
5
3
𝑝𝑟𝑒𝑣
𝑐
𝑐
𝑎,𝑑,𝑏,𝑐,𝑓
𝑐𝑜𝑠𝑡
4
𝑝𝑟𝑒𝑣
𝑓
𝑎,𝑑,𝑏,𝑐,𝑓,𝑒
𝑐𝑜𝑠𝑡
𝑝𝑟𝑒𝑣

COMP90038 – Algorithms and Complexity
Lecture 20
Analysis of Prim’s Algorithm
• First, a crude analysis: For each node, we look through the edges to find those incident to the node, and pick the one with the smallest cost. Thus we get
Ο |𝑉| M |𝐸| . However, we are using clever data structures.
• Using adjacency lists for the graph and a min-heap for the priority queue, we perform 𝑉 − 1 heap deletions (each at a cost of Ο log |𝑉| ) and |𝐸| updates of priorities (again, each at a cost of Ο log |𝑉| ).
• Altogether 𝑉 − 1 + |𝐸| Ο log|𝑉| ).
• Since, in a connected graph, 𝑉 − 1 ≤ |𝐸|, this is Ο 𝐸 log |𝑉| .

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• Pick the first node as the initial one.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑔
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We take the first node out of the queue & update the costs.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑔
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
4
8
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Prim’s Algorithm: Example
• We eject the node with the lowest cost & update the queue.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑔
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
4
8
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑏
𝑐𝑜𝑠𝑡
8
8
10
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑏
𝑏
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑏,𝑐
𝑐𝑜𝑠𝑡
2
10
1
∞
𝑝𝑟𝑒𝑣
𝑐
𝑏
c
𝑛𝑖𝑙
𝑎,𝑏,𝑐,𝑓
𝑐𝑜𝑠𝑡
2
5
2
𝑝𝑟𝑒𝑣
𝑐
𝑓
𝑓

COMP90038 – Algorithms and Complexity Lecture 20
Dijkstra’s Algorithm
• Another classical greedy weighted-graph algorithm is Dijkstra’s algorithm, whose overall structure is the same as Prim’s.
• Recall that Floyd’s algorithm gave us the shortest paths, for every pair of nodes, in a (directed or undirected) weighted graph. It assumed an adjacency matrix representation and had a complexity of Ο |𝑉|’ .
• Dijkstra’s algorithm is also a shortest-path algorithm for (directed or undirected) weighted graphs. It finds all shortest paths from a fixed start node. Its complexity is the same as that of Prim’s algorithm.

COMP90038 – Algorithms and Complexity Lecture 20
Dijkstra’s Algorithm

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• On the first loop, we only create the table.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• Then we pick the first node as the initial one.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• We take the first node out of the queue & update the distance.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
∞
4
1
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• Eject node with shortest distance from queue; update all path by +1
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
∞
4
1
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
3
2
5
6
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑑
𝑑

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• The next node will be the one with the shortest path overall.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
∞
4
1
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
3
2
5
6
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑑
𝑑
𝑎,𝑑,𝑐
𝑐𝑜𝑠𝑡
3
4
5
𝑝𝑟𝑒𝑣
d
𝑐
𝑐

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• Now we continue evaluating from (𝑐).
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
∞
4
1
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
3
2
5
6
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑑
𝑑
𝑎,𝑑,𝑐
𝑐𝑜𝑠𝑡
3
4
5
𝑝𝑟𝑒𝑣
d
𝑐
𝑐
𝑎,𝑑,𝑐,𝑏
𝑐𝑜𝑠𝑡
4
5
𝑝𝑟𝑒𝑣
𝑐
𝑐

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• We arrive at our last decision.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
∞
4
1
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
3
2
5
6
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑑
𝑑
𝑎,𝑑,𝑐
𝑐𝑜𝑠𝑡
3
4
5
𝑝𝑟𝑒𝑣
d
𝑐
𝑐
𝑎,𝑑,𝑐,𝑏
𝑐𝑜𝑠𝑡
4
5
𝑝𝑟𝑒𝑣
𝑐
𝑐
𝑎,𝑑,𝑐,𝑏,𝑒
𝑐𝑜𝑠𝑡
5
𝑝𝑟𝑒𝑣
𝑐

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• The complete tree is 𝑎,𝑑,𝑐,𝑏,𝑒,𝑓 .
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑐𝑜𝑠𝑡
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
∞
4
1
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑑
𝑐𝑜𝑠𝑡
3
2
5
6
𝑝𝑟𝑒𝑣
𝑑
𝑑
𝑑
𝑑
𝑎,𝑑,𝑐
𝑐𝑜𝑠𝑡
3
4
5
𝑝𝑟𝑒𝑣
d
𝑐
𝑐
𝑎,𝑑,𝑐,𝑏
𝑐𝑜𝑠𝑡
4
5
𝑝𝑟𝑒𝑣
𝑐
𝑐
𝑎,𝑑,𝑐,𝑏,𝑒
𝑐𝑜𝑠𝑡
5
𝑝𝑟𝑒𝑣
𝑐
𝑎,𝑑,𝑐,𝑏,𝑒,𝑓
𝑐𝑜𝑠𝑡
𝑝𝑟𝑒𝑣
1

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Tracing Paths
• The array 𝑝𝑟𝑒𝑣 is not really needed, unless we want to retrace the shortest paths from node 𝑎:
• This is referred to as the shortest-path tree.

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• Pick the first node as the initial one.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑔
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• We take the first node out of the queue & update the distances.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑔
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
4
8
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙

COMP90038 – Algorithms and Complexity
Lecture 20
Dijkstra’s Algorithm: Example
• We eject the node with the lowest distance & update the queue.
Tree 𝑇
𝑎
𝑏
𝑐
𝑑
𝑒
𝑓
𝑔
𝑐𝑜𝑠𝑡
0
∞
∞
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎
𝑐𝑜𝑠𝑡
4
8
∞
∞
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑎
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑏
𝑐𝑜𝑠𝑡
8
12
14
∞
∞
𝑝𝑟𝑒𝑣
𝑎
𝑏
𝑏
𝑛𝑖𝑙
𝑛𝑖𝑙
𝑎,𝑏,𝑐
𝑐𝑜𝑠𝑡
10
14
9
∞
𝑝𝑟𝑒𝑣
𝑐
𝑏
c
𝑛𝑖𝑙
𝑎,𝑏,𝑐,𝑓
𝑐𝑜𝑠𝑡
10
14
11
𝑝𝑟𝑒𝑣
𝑐
𝑏
𝑓

COMP90038 – Algorithms and Complexity Lecture 20
Negative Weights
• In our example, we used positive weights, and for good reason: Dijkstra’s algorithm may not work otherwise!
• In this example, the greedy pick—choosing the edge from 𝑎 to 𝑏—is clearly the wrong one.
• The Bellman-Ford algorithm will find single-source shortest paths in arbitrary weighted graphs (but is also more costly to run).
• And if the graph has a cycle with accumulated negative weight then none of these algorithms work—they don’t really make sense.

COMP90038 – Algorithms and Complexity Lecture 20
Coming Up Next
• Huffman encoding for data compression (Levitin Section 9.4)

Related Posts