5.7: Weighted Graphs and Dijkstra's Algorithm

Investigate!

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
Saint Mary's	0	3	7	-	-	-	17
Holy Cross		0	6	-	11	-	-
Notre Dame			0	8	-	14	-
Ranjan's House				0	-	15	22
Chocolate Cafe					0	12	15
Crooked Ewe						0	-
Airport							0

Definition

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.

Dijkstra's algorithm

• Input: a weighted graph, $G$, with a source vertex $s$
  • for each vertex $v$ in $G$:
    • $dist(v):=\infty$
    • $prev(v):=undefined$
  • $dist(s):=0$
  • $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$
      • $alt:=dist(u)+w(u,v)$
      • if $alt<dist(v)$
        • $dist(v):=alt$
        • $prev(v):=u$
  • return $dist(), prev()$

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.

Exercise $\PageIndex{1}$

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.

Theorem $\PageIndex{2}$

Dijkstra's Algorithm finds a shortest path between two vertices in a simple undirected weighted graph.

Proof

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

$length(P_x)+w(x,y)\leq length(P)$,

and by the induction hypothesis

$dist(x)+w(x,y)\leq length(P)$.

Since $y$ is adjacent to $x$, the algorithm recalculates $dist(y)$, so

$dist(y)\leq dist(x)+w(x,y)$.

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.