## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

# 43. Dijkstra’s Algorithm Challenges Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

### 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 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.