Studio 13: Shortest Paths

This week's studio will give practice with Dijkstra's Algorithm and explore a variant for graphs with bounded edge weights.

Part A: Practice with Dijkstra's Algorithm

Pseudocode for Djikstra's Algorithm:

Dijkstra(Graph, source)
  dist[source] <- 0                           // Initialization
  create vertex set Q

    for each vertex v in Graph:           
      if v ≠ source
        dist[v] <- INFINITY                   // Unknown distance from source to v
        prev[v] <- UNDEFINED                  // Predecessor of v

      Q.addWithPriority(v, dist[v])

    while Q is not empty:                     // The main loop
      u <- Q.extractMin()                     // Remove and return best vertex
      for each neighbor v of u:               // only v that are still in Q
        alt <- dist[u] + length(u, v) 
        if alt <- dist[v]
          dist[v] <- alt
          prev[v] <- u
          Q.decreasePriority(v, alt)

  return dist, prev


Question A1: View the graph in "Logial Representation". Write it out in "Adjacency List Representation". Check your work by clicking the corresponding bubble in the visualizer.

  • Starting from node 0, run Djikstra’s algorithm by hand. Any time you need to decide between two nodes that are tied, choose the node with the smaller number.

Question A2: What are the distances assigned by Dijkstra's algorithm to each vertex?

Question A3: Which edges are present in the resulting shortest-path tree?

  • In the 'Start Vertex' box, enter 0 and click 'Run Djikstra'.

Question A4: Do the results in the visualizer match the results you got by hand? If not, go back and try to figure out where you diverged. Discuss your results with your group and TA.

Part B: Shortest Paths with Bounded Edge Weights

We saw in lecture that Dijkstra's Algorithm requires non-negative edge weights but no other restrictions on edge weights are required. We will now explore the single-source shortest-path problem (aka the SSSP problem) in graphs where edge weights are non-negative integers bounded by a constant. We call this the Single-Source Shortest-Paths - Bounded Edge Weights problem, or SSSP-BEW problem for short.

Let G be a directed, edge-weighted graph such that every edge's weight is in the set {0, 1, . . . , W}, where W is a non-negative integer.

Question B1: What is the longest possible path between two vertices v and v’ in G, given that there are n total vertices?

Question B2: Give a modified version of Dijkstra’s algorithm that solves the SSSP-BEW problem in time O(nW + m) for a graph with n vertices and m edges.

Question B3: Justify the correctness of your algorithm. You do not need a full formal proof, but your justification should convince you, your group, and your TA.

Question B4: What happens to the runtime of your modified algorithm (not the standard Dijkstra's Algorithm) when W is no longer constrained to be a constant integer? To be concrete, compare the runtime of your algorithm to the runtime of the standard Dijkstra's Algorithm both when W is constant relative to n and when it is not (say, when it is n^2) .

Part C: Exploring Negative Weights

Now let’s explore what happens when we try to run Dijkstra’s Algorithm on a graph with negative edge weights.

graph for neg-weight Dijkstra's

Question C1: Run Dijkstra’s on the graph above using a as the start vertex and describe exactly where it fails; that is, where it dictates an action that will lead to an incorrect result.

To correct for this, suppose you found the minimum (most negative) edge weight in the graph, min, and added |min| to each edge in the graph, thus making every edge in the graph non-negative. Call this graph with all non-negative weights G’.

Question C2: Does running Dijkstra’s on G’ produce the shortest paths for G? Justify the correctness of this approach or provide a counterexample if applicable.