5.7: Weighted Graphs and Dijkstra's Algorithm
- Page ID
In the table, the time it takes to travel between various locations by bus in South Bend is given. Incorporate this information in a graph, and then find shortest paths from the airport to every other location.
|Saint Mary's||Holy Cross||Notre Dame||Ranjan's House||Chocolate Cafe||Crooked Ewe||Airport|
A graph with a number (usually positive) assigned to each edge is called a weighted graph. (A graph without weights can be thought of as a weighted graph with all weights equal to 1.) We denote the weight between vertices \(u\) and \(v\) by \(w(u,v)\).
In the previous example, the weights represented distances. What else could we represent using weights?
In many situations, we want to find a shortest path (or path of least weight) between two locations. Dijkstra's algorithm gives us a way to do this.
- Input: a weighted graph, \(G\), with a source vertex \(s\)
- for each vertex \(v\) in \(G\):
- \(Q:=\) set of all vertices in \(G\)
- while \(Q\) is not empty:
- \(u:=\) vertex in \(Q\) with smallest distance
- remove \(u\) from \(Q\)
- for each neighbor \(v\) of \(u\)
- if \(alt<dist(v)\)
- return \(dist(), prev()\)
- for each vertex \(v\) in \(G\):
Remark: If you only want to know the distance from the source to a particular vertex, you can terminate the algorithm when that vertex is removed from \(Q\).
Challenge: Find a big-O estimate for the number of operations (additions and comparisons) used by Dijkstra's algorithm.
Saint Mary's once had tunnels connecting various buildings on campus. The tunnels and their lengths are as follows (and definitely not accurate): Regina to McCandless (400 ft), Regina to Student Center (200), McCandless to Student Center (100), McCandless to Angela (500), Student Center to Angela (800), Student Center to Library (1000), Angela to Library (200), Angela to Madeleva (600), Library to Madeleva (300). Find a shortest path from Regina to Madeleva using Dijkstra's Algorithm.
Dijkstra's Algorithm finds a shortest path between two vertices in a simple undirected weighted graph.
We will prove the theorem by induction on \(|V\setminus Q|\). The first vertex removed from \(Q\) is \(s\). In this case \(|V\setminus Q|=1\) and Dijkstra's algorithm tells us that the distance from the source to \(s\) (ie from \(s\) to itself) is 0. Therefore, the base case is true.
The inductive hypothesis is that for any vertex not in \(Q\), the distance assigned to that vertex by the algorithm is in fact the minimum distance from the source to that vertex.
Let \(u\) be the most recent vertex removed from \(Q\). By the inductive hypothesis, the algorithm has provided the minimum distance from the source for every vertex in \(V\setminus Q\) besides \(u\).
Suppose by contradiction that a shortest path \(P\) from \(s\) to \(u\) has length less than \(dist(u)\). In other words, \(length(P)<dist(u)\). Let \(xy\) be the first edge along \(P\) that isn't in \(V\setminus Q\) and let \(P_x\) be the sub-path of \(P\) from \(s\) to \(x\). Then
and by the induction hypothesis
Since \(y\) is adjacent to \(x\), the algorithm recalculates \(dist(y)\), so
Combining these inequalities, we see that \(dist(y)<dist(u)\). But the algorithm removed \(u\) from \(Q\) and not \(y\), so we must have that \(dist(u)\leq dist(y)\). This is a contradiction, and the proof is complete.