What do the following apps and systems have in common

- Google Maps,
- Skyscanner,
- GOARN,
- mobile phone networks

?

There is at least one such thing – there is a really high chance that all of them use Dijkstra’s algorithm to figure out the shortest distance between 2 locations on Earth, to track how fast and in what direction diseases spread around the world and how to efficiently distribute the phone calls throughout the network.

Speaking of that in a bit more technical way, an objective of Dijkstra’s algorithm is to find the shortest path between any 2 vertices in a graph.

Here’s a really good YouTube video explaining that algorithm in detail:

And here’s an implementation of that algorithm in Swift:

```
struct Edge {
let destination: Int
let weight: Int
}
struct Graph {
let numberOfVertices: Int
var adjacencyList: [[Edge]] = []
init(numberOfVertices: Int) {
self.numberOfVertices = numberOfVertices
self.adjacencyList = Array(repeating: [], count: numberOfVertices)
}
mutating func addEdge(source: Int, destination: Int, weight: Int) {
adjacencyList[source].append(Edge(destination: destination, weight: weight))
}
}
func dijkstra(graph: Graph, source: Int) -> [Int] {
var distances = Array(repeating: Int.max, count: graph.numberOfVertices)
var priorityQueue = [(vertex: Int, distance: Int)]()
distances[source] = 0
priorityQueue.append((source, 0))
while !priorityQueue.isEmpty {
priorityQueue.sort { $0.distance < $1.distance }
let current = priorityQueue.removeFirst()
for edge in graph.adjacencyList[current.vertex] {
let newDistance = current.distance + edge.weight
if newDistance < distances[edge.destination] {
distances[edge.destination] = newDistance
priorityQueue.append((edge.destination, newDistance))
}
}
}
return distances
}
var graph = Graph(numberOfVertices: 5)
graph.addEdge(source: 0, destination: 1, weight: 6)
graph.addEdge(source: 0, destination: 3, weight: 1)
graph.addEdge(source: 1, destination: 0, weight: 6)
graph.addEdge(source: 1, destination: 3, weight: 2)
graph.addEdge(source: 1, destination: 2, weight: 5)
graph.addEdge(source: 1, destination: 4, weight: 2)
graph.addEdge(source: 2, destination: 1, weight: 5)
graph.addEdge(source: 2, destination: 4, weight: 5)
graph.addEdge(source: 3, destination: 0, weight: 1)
graph.addEdge(source: 3, destination: 1, weight: 2)
graph.addEdge(source: 3, destination: 4, weight: 1)
graph.addEdge(source: 4, destination: 1, weight: 2)
graph.addEdge(source: 4, destination: 2, weight: 5)
graph.addEdge(source: 4, destination: 3, weight: 1)
let distances = dijkstra(graph: graph, source: 0)
for (vertex, distance) in distances.enumerated() {
print("Shortest distance from 0 to \(vertex) is \(distance)")
}
```

You can find that code in my GitHub repo here https://github.com/DamianMarkowski/algorithms-and-data-structures/blob/master/Dijkstras-algorithm/Dijkstras-algorithm.playground/Contents.swift as well.