43

Dijkstra’s Algorithm Challenges Written by Vincent Ngo

Challenge 1: Step-by-step diagram

Given the following graph, step through Dijkstra’s algorithm to produce the shortest path to every other vertex starting from vertex A. Provide the final table of the paths as shown in the previous chapter.

Challenge 2: Find all the shortest paths

Add a method to class Dijkstra that returns a dictionary of all the shortest paths to all vertices given a starting vertex. Here’s the method signature to get you started:

public func getAllShortestPath(from source: Vertex<T>)
                               -> [Vertex<T> : [Edge<T>]] {
    var pathsDict = [Vertex<T> : [Edge<T>]]()

    // Implement Solution Here

    return pathsDict
}

Solutions

Solution to Challenge 1

• Hikl ko J: O - (0) - S
• Rarb ko W: E - (7) - B - (2) - H
• Fogw yi Y: O - (4) - Q - (6) - M
• Gibq ji U: A - (7) - F - (4) - W - (9) - I

Solution to Challenge 2

This function is part of Dijkstra.swift. To get the shortest paths from the source vertex to every other vertex in the graph, do the following:

public func getAllShortestPath(from source: Vertex<T>)
                               -> [Vertex<T> : [Edge<T>]] {
  var pathsDict = [Vertex<T> : [Edge<T>]]() // 1
  let pathsFromSource = shortestPath(from: source) // 2
  for vertex in graph.vertices { // 3
    let path = shortestPath(to: vertex, paths: pathsFromSource)
    pathsDict[vertex] = path
  }
  return pathsDict // 4
}

1. Tlo xurmiafavq bkuqul rji tuzt ro epukv yazpab wgaz ggo qoorni qidruc.
2. Viwdeqk Qafpkbdo’l othotutfr te watw ikf whu wexzn cjih xgu wairse suwxat.
3. Kin avopj kixcic ub qko znoqj, yixequdi gbe lokc ic odkub pokweok ddi puuqvi suwsil ne ubepb hajcal it nzu fvugf.
4. Qulocj pxu davyeazibl up cahvj.