Shortest Paths

1. Reading
2. Video
3. Slides
4. Practice Problems
5. Learning Block

1 Reading

2 Video

Here is a video lecture for the slides below.

The video contains sections on

Single source shortest paths (0:08)
BFS doesn't work for weights (1:15)
Dijkstra's algorithm (3:06)
Dijkstra's Algorithm: Idea (4:03)
The Algorithm (4:48)
Important features (6:52)
Example #1 (7:41)
Features, part 2 (14:45)
Interpreting the Results (16:24)
Stopping Short (17:22)
Example #2 (18:42)
Example #3 (21:00)
A Greedy Algorithm (22:59)
Where are We? (25:36)
Efficiency, first approach (26:01)
Improving asymptotic running time (29:00)
Efficiency, second approach (31:56)
Dense vs. sparse again (34:48)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=3bb09c5f-9988-440e-aff2-acde016b834f

3 Slides

You can download the slides in pdf or PowerPoint.

4 Practice Problems¹

Explain why it is sometimes more efficient to compute the distance from a single source to all other nodes, even though a particular query may be answered with a partial solution.
Step through Dijkstra's algorithm to calculate the single-source shortest paths from A to every other vertex. Show your steps in the table below. Cross out old values and write in new ones, from left to right within each cell, as the algorithm proceeds. Also list the vertices in the order which you marked them known. Finally, indicate the lowest-cast path from node A to node G.
Given the graph above, list one possible order that vertices in the graph above would be processed if a breadth first traversal is done starting at A.
True or false. Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.

5 Learning Block

Summary
- BFS doesn't work on weighted graphs (shortest path may not be the one with the fewest edges)
- Dijkstra's algorithm can shortest paths from source node to all other nodes in the graph in \(O(|V|^2)\) time (or \(O(|V|\log |V| + |E|\log |V|)\) with a priority queu)
- It does this by keeping track of a set of known nodes and repeatedly adding a node to this known set
  - The added node is the unknown node the smallest distance away from the source
  - When a node is added, its outgoing edges are examined to see if they result in a shorter path to other nodes in the graph
  - (The algorithm also keeps track of the shortest-path-so-far to each node)
Questions?
Form question
Exercise in pods:
- Perhaps using this BFS implementation as a starting point, implement Dijkstra's algorithm. The Java PriorityQueue does not have a decreaseKey operation, so use IndexMinPQ from algs4. Here is a starter project you should use: ./dijkstras.zip. Here is documentation on relevant algs4 classes: EdgeWeightedGraph, DirectedEdge, IndexMinPQ.

Solution:

import java.util.LinkedList;

import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.IndexMinPQ;
import edu.princeton.cs.algs4.StdOut;

public class Dijkstras {
    private double[] distTo; // distTo[v] = distance of shortest s->v path
    private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
    private IndexMinPQ<Double> pq; // priority queue of vertices

    public Dijkstras(EdgeWeightedDigraph G, int s) {
        // initialize data structures
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        boolean[] known = new boolean[G.V()];
        pq = new IndexMinPQ<>(G.V());

        // initialize distances
        for (int v = 0; v < known.length; v++) {
            if (v != s) {
                distTo[v] = Double.POSITIVE_INFINITY;
            }
            pq.insert(v, distTo[v]);
        }

        // run algorithm
        while (!pq.isEmpty()) {
            int v = pq.delMin();
            known[v] = true;
            for (DirectedEdge e : G.adj(v)) {
                if (!known[e.to()] && distTo[v] + e.weight() < distTo[e.to()]) {
                    distTo[e.to()] = distTo[v] + e.weight();
                    edgeTo[e.to()] = e;
                    pq.decreaseKey(e.to(), distTo[e.to()]);
                }
            }
        }
    }

    /**
     * Returns the length of a shortest path from the source vertex s to
     * vertex v.
     */
    public double distTo(int v) {
        return distTo[v];
    }

    /**
     * Returns true if there is a path from the source vertex s to vertex v.
     */
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    /**
     * Returns a shortest path from the source vertex s to vertex v.
     */
    public Iterable<DirectedEdge> pathTo(int v) {
        if (!hasPathTo(v))
            return null;
        LinkedList<DirectedEdge> path = new LinkedList<>();
        DirectedEdge e = edgeTo[v];
        while (e != null) {
            path.addFirst(e);
            e = edgeTo[e.from()];
        }
        return path;
    }

    public static void main(String[] args) {
        In in = new In("tinyEWD.txt");
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
        int s = 0;

        // compute shortest paths
        Dijkstras sp = new Dijkstras(G, s);

        // print shortest path
        for (int t = 0; t < G.V(); t++) {
            if (sp.hasPathTo(t)) {
                StdOut.printf("%d to %d (%.2f)  ", s, t, sp.distTo(t));
                for (DirectedEdge e : sp.pathTo(t)) {
                    StdOut.print(e + "   ");
                }
                StdOut.println();
            } else {
                StdOut.printf("%d to %d         no path\n", s, t);
            }
        }
    }

    /**
     * Expected output:
     * 0 to 0 (0.00)  
     * 0 to 1 (1.05)  0->4  0.38   4->5  0.35   5->1  0.32   
     * 0 to 2 (0.26)  0->2  0.26   
     * 0 to 3 (0.99)  0->2  0.26   2->7  0.34   7->3  0.39   
     * 0 to 4 (0.38)  0->4  0.38   
     * 0 to 5 (0.73)  0->4  0.38   4->5  0.35   
     * 0 to 6 (1.51)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   
     * 0 to 7 (0.60)  0->2  0.26   2->7  0.34
     */
}

Footnotes:

Solutions:

This can happen if multiple queries are made regarding a single source. One calculation of all solutions is less expensive than computing several partial solutions; some aspects of different solutions are shared.
Completed table:
For a given distance, the vertices can be in any order.

Distance away 0 1 2 3 4

A B E G F C D H
False. The number of edges in a shortest path will affect the amount its cost increases from adding a constant to all edge weights.

Shortest Paths

Table of Contents

1 Reading

2 Video

3 Slides

4 Practice Problems1

5 Learning Block

Footnotes:

4 Practice Problems¹