# Understanding Dijkstra's Shortest Path Algorithm with Swift

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**

The challenge with graphs is knowing how a vertex relates to other objects. Consider the social networking website, **LinkedIn**. With LinkedIn, each profile can be thought of as a single vertex that may be connected with other vertices.

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

**FINDING YOUR WAY**

Shortest paths can also be seen with map-based services like *Google Maps*. Users frequently use Google Maps to ascertain driving directions between two points. As we know, there are often multiple ways to get to any destination. The shortest route will often depend on various factors such as traffic, road conditions, accidents and time of day. In graph theory, these external factors represent edge weights.

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**

Edsger Dijkstra’s algorithm was published in 1959 and is designed to find the shortest path between two vertices in a directed graph with non-negative edge weights. Let’s review how to implement this in Swift.

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**

Throughout our journey, we’ll track each node visit in a custom data structure called Path. The total will manage the cumulative edge weight to reach a particular destination. The previous property will represent the Path taken to reach that Vertex:

//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**

With all the *graph* components in place, let’s see how it works. The method processDijkstra accepts the vertices source and destination as parameters. It also returns a Path. Since it may not be possible to find the destination, the return value is declared as a Swift *optional:*

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

...

}

**BUILDING THE FRONTIER**

As discussed, the key to understanding Dijkstra’s algorithm is knowing how to traverse the graph. To help, we’ll introduce a few rules and a new concept called *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:

...

//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:

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**

Dijkstra’s algorithm can be described as “single source” because it calculates the path to every vertex. In our example, we’ve preserved this information in the finalPaths array.

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**

Dijkstra’s algorithm is an elegant solution to a complex problem. Even though we’ve used it effectively, we can **improve its performance** by making a few adjustments. We’ll analyze those details in the next chapter.

# Get the free iOS Interview Worksheet

Need to prepare for your next technical interview? We’re offering a free 5-page download of tips and tricks to help you be successful. When you sign up using **this link**, we’ll send you the worksheet in PDF format.