Home iOS & Swift Books Data Structures & Algorithms in Swift

43
Dijkstra’s Algorithm Challenges Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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

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
}

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.