# CS代考 COMP90038 Algorithms and Complexity – cscodehelp代写

COMP90038 Algorithms and Complexity
Greedy Algorithms: Prim and Dijkstra
Olya Ohrimenko
(Slides from Harald Søndergaard)
Lecture 20
Semester 2, 2021
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 1 / 22

Announcements
Assignment 2 is out on LMS.
Olya’s consultation session (Zoom link via LMS):
Tuesday October 12, 2:30 – 3:30 pm
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 2 / 22

Last two lectures: Dynamic Programming
We looked at dynamic programming for knapsack problem and two graph problems:
Warshall algorithm: Computing the transitive closure of a directed graph; and
Floyd’s algorithm: Finding shortest distances in weighted directed graphs.
Python code available for all algorithms on LMS.
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 3 / 22

Greedy Algorithms
A natural strategy to problem solving is to make decisions based on what is the locally best choice.
Suppose we have coin denominations 25, 10, and 1, and we want to change 35 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 35 cents. (In this case we use 25+10 cents.)
This greedy strategy will work for 35 cents but not always. For which of these it will not work? (a) 50 (b) 30 (c) 5.
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 4 / 22

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.
Here we shall look at
Prim’s algorithm for finding minimum spanning trees Dijkstra’s algorithm for single-source shortest paths
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 5 / 22

Spanning Trees
Recall that a tree is a connected graph with no cycle.
A spanning tree of a graph ⟨V,E⟩ is a tree ⟨V,E′⟩ with E′ ⊆ E.
The graph has eight different spanning trees:
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 6 / 22

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.
a6c5e 541234 b2d4f
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 7 / 22

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.
a6c5e 541234 b2d4f
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 8 / 22

Minimum Spanning Trees: Prim’s Algorithm
Prim’s algorithm is an example of a greedy algorithm.
It constructs a sequence of subtrees T, 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:
function Prim(⟨V,E⟩) VT ←{v0}
ET ←∅
for i ← 1 to |V | − 1 do
findaminimum-weightedge(v,u)∈VT ×(VVT) VT ←VT ∪{u}
ET ←ET ∪{(v,u)}
return ET
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 9 / 22

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 (v,u)?
A standard way to do this is to organise the nodes that are not yet included in the spanning tree T as a priority queue, organised in a min-heap by edge cost.
The information about which nodes are connected in T can be captured by an array prev of nodes, indexed by V . Namely, when (v , u) is included, this is captured by setting prev [u] = v .
Algorithms and Complexity (Sem 2, 2021) Prim and Dijkstra © University of Melbourne 10 / 22

Prim’s Algorithm
function Prim(⟨V,E⟩) for each v ∈ V do
cost[v] ← ∞ prev[v] ← nil
pick initial node v0
cost[v0] ← 0
Q ← InitPriorityQueue(V ) while Q is non-empty do
u ← EjectMin(Q) foreach(u,w)∈E do
⊲ priorities are cost values