Shortest paths and Minimum Spanning Tree
CS 124 Section 2 Zuzanna Skoczylas
•We use a queue (first-in first-out) to keep track of which vertices have already been visited. Unlike Depth-first search, we visit all of our closest neighbors before moving on to further ones.
•Can be used to find the shortest path when all the edge weights are equal to 1.
• Run-time: O(|V | + |E|)
Breadth-first search (BFS)
BFS
• Find shortest paths in graphs with any positive edge weights from given point. • When a node is popped off the heap, that means we have our final answer for
that node’s distance and path from the source.
• NotethatDijkstra’salgorithmdoesnotworkfornegativeedgeweights!
• Run-time:O(|V|·deleteMin+|E|·insert).
• TherunningtimeofDijkstra’salgorithmdependsontheimplementationofthe heap H. For each vertex, we perform a delete min, while for each edge we perform an insertion.
Dijkstra’s Algorithm
Dijkstra’s Algorithm
• Find shortest paths in graphs with any positive or negative edge weights from given point.
• Can be used to find negative cycles in a graph. • Run-time:O(|V||E|)
Bellman Ford Algorithm
Bellman Ford
A tree is an undirected graph T = (V, E) satisfying all of the following conditions: • T is connected,
• T is acyclic,
• |E|=|V|−1.
Any two conditions above imply the third.
A spanning tree of an undirected graph G = (V,E) is a subgraph which is a tree and which connects all the vertices. (If G is not connected, G has no spanning trees.)
A minimum spanning tree is a spanning tree whose total sum of edge costs is minimum.
Minimum Spanning Trees
Minimum Spanning Tree – Algorithms
Prim’s Algorithm
Kruskal’s Algorithm
Exercise
(1) You are given a map of a city with houses and a task of planning telephone lines. Each house must be connected to each other house via telephone lines. Each segment of telephone line is between two houses. You want to use as little length of telephone line as you can.
(2) You are given the same problem, but this time the endpoints of the line can be located not only in houses.
Which of these problems is a Minimum Spanning Tree?
Let X be a subgraph of 𝐺 = (𝑉, 𝐸) such that 𝑋 is contained in some MST of 𝐺. Let 𝑆 ⊂ 𝑉 be a cut such that no edge of 𝑋 has one endpoint in S. Suppose e has minimum weight among the edges crossing the cut: then 𝑋 ∪ {𝑒} is contained in some MST of 𝐺. This means that it’s safe to add 𝑒 to our partial MST and still be on-track to finding an MST.
Cut property
Exercise
Use the cut property to show that given any vertex, the edge extending out of that vertex with the lightest weight is contained in some MST.
Let u be the vertex we are considering, and let 𝑣_1,𝑣_2…𝑣_𝑘be the neighbors of 𝑢. Let 𝑋 = ∅ and 𝑆 = {𝑢} in the cut property above. Clearly, 𝑋 is a subgraph of some MST because the empty graph is a subgraph of all graphs. Our cut is between the sets 𝑆 and 𝑉 − 𝑆, and clearly no edges in our empty 𝑋 crosses that cut. The only edges that cross this cut are (𝑢, 𝑣_1 ), (𝑢, 𝑣_2 ), . . . , (𝑢, 𝑣_𝑘 )and thus by the cut property, the lightest one of them must be contained in some MST.
Solution
In a city there are N houses, each of which is in need of a water supply. It costs 𝑊! dollars to build a well at house 𝑖, and it costs 𝐶!” to build a pipe in between houses
𝑖 and 𝑗. A house can receive water if either there is a well built there or there is some path of pipes to a house with a well. Give an algorithm to find the minimum amount of money needed to supply every house with water.
Problem 1
There are n students standing in a playground trying to split into two teams to play kickball. No one cares that the teams have equal, or even nearly equal sizes, but the students do care that they are not on the same team as any of their mortal enemies. You are given a set of m enemy links, which are mutual. If person A has an enemy link with B, they absolutely cannot be on the same team. Give an algorithm to partition the students into two teams such that no enemies are on the same team. If this is not possible, return “Impossible”.
Problem 2
(CLRS 21.3-6) Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge (one of minimum weight) crossing the cut. Conclude that this implies that if a graph has unique edge weights, then it has a unique minimum spanning tree.
Problem 3