Understanding Dijkstra's Shortest Path Algorithm with Swift

Wayne Bishop
Dec 15, 2018 · 5 min read

In the previous chapter in our series, we saw how graphs show the relationship between two or more objects. Because of their flexibility, graphs are used in a wide range of applications including map-based services, networking and social media. Popular models may include roads, traffic, people and locations. In this chapter, we’ll review how to search a graph and will implement a popular algorithm called Dijkstra’s shortest path.

MAKING CONNECTIONS

One feature of LinkedIn is the ability to introduce yourself to new people. Under this scenario, LinkedIn will suggest routing your message through a shared connection. In graph theory, the most efficient way to deliver your message is called the shortest path.

The shortest path from vertex A to C is through vertex B.

FINDING YOUR WAY

The shortest path from vertex A to C is through vertex A.

This example illustrates some key points we’ll see in Dijkstra’s algorithm. In addition to there being multiple ways to arrive at vertex C from A, the shortest path is assumed to be through vertex B. It’s only when we arrive to vertex C from B, we adjust our interpretation of the shortest path and change direction (e.g. 4 < (1 + 5)). This change in direction is known as the greedy approach and is used in similar problems like the traveling salesman.

INTRODUCING DIJKSTRA

Even though our model is labeled with key values and edge weights, our algorithm can only see a subset of this information. Starting at the source vertex, our goal will be to traverse the graph.

USING PATHS

//the path class maintains objects that comprise the "frontier"class Path {

var total: Int
var destination: Vertex
var previous: Path?
//object initialization
init(){
destination = Vertex()
total = 0
}
}

DECONSTRUCTING DIJKSTRA

//Dijkstra’s shortest path algorithmfunc processDijkstra(source: Vertex, destination: Vertex) -> Path? {
...
}

BUILDING THE FRONTIER

        var frontier = Array<Path>()
var finalPaths = Array<Path>()

//use source edges to create the frontier
for e in source.neighbors {

let newPath: Path = Path()

newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight

//add the new path to the frontier
frontier.append(newPath)

}

The algorithm starts by examining the source vertex and iterating through its list of neighbors. Recall from the previous chapter, each neighbor is represented as an edge. For each iteration, information about the neighboring edge is used to construct a new Path. Finally, each Path is added to the frontier:

The frontier visualized as a list.
...
//construct the best path
var bestPath: Path = Path()

while frontier.count != 0 {

//support path changes using the greedy approach
bestPath = Path()
var pathIndex: Int = 0
for x in 0..<frontier.count {

let itemPath: Path = frontier[x]

if (bestPath.total == 0) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}

}
...

As shown, we’ve used the bestPath to build a new series of Paths. We’ve also preserved our visit history with each new object. With this section completed, let’s review our changes to the frontier:

The frontier after visiting two additional vertices.

At this point, we’ve learned a little more about our graph. There are now two possible paths to vertex D. The shortest path has also changed to arrive at vertex C. Finally, the Path through route A-B has been removed and has been added to a new structure named finalPaths.

A SINGLE SOURCE

The finalPaths once the frontier reaches zero. As shown, every permutation from vertex A is calculated.

Based on this data, we can see the shortest path to vertex E from A is A-D-E. The bonus is that in addition to obtaining information for a single route, we’ve also calculated the shortest path to each node in the graph.

ASYMPTOTICS

Get the free iOS Interview Worksheet

Swift Algorithms & Data Structures

Modern Code, Illustrations & Computer science

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store