Understanding Dijkstra's Shortest Path Algorithm with Swift

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:The frontier visualized as a list….//construct the best pathvar 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 SOURCEDijkstra’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.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.ASYMPTOTICSDijkstra’s algorithm is an elegant solution to a complex problem.. More details

Leave a Reply