Introduction
Finding the shortest route is one of the core topics in computer science. There are many algorithms for finding the shortest route (Dijkstra, A*, Bellman-Ford...) and choosing the best one depends on the size of the search space and the cost of finding the best solution versus using an approximation.
The scope of this article is to only cover two algorithms for solving said problem, namely using depth-first search and the Dijkstra's algorithm. Without further ado, let us first revisit the definition of a graph.
What is a Graph?
Graphs is a connected map of nodes. They are either acyclic meaning that every connection between two nodes is bidirectional, or cyclic meaning that the connections are directional. Think of graphs as a map of nodes representing locations, cities or even planets. Each node is connected to a set of adjacent nodes through edges. Every edge is assigned a cost (ex. time, energy...) of going from one side of the edge to the other.
Depth-first search:
The shortest distance from node A to node B, represented as dist(A,B) is the shortest path among all possible paths connecting A to B.
In depth-first search, we use a set to keep track of the visited nodes along the path starting from node A and expanding along the edges leading to neighboring nodes. The set is required to avoid going through cycles.
Below is Kotlin pseudocode for finding the shortest path (without tracking its actual nodes):
fun shortestPath(start: Node, nodeB: Node, cumulativePathWeights: Int, visitedNodes: Stack<Node>): Int {
if (start == nodeB) {
return cumulativePathWeights
}
var minDist = Int.MAX_VALUE
if (start !in visitedNodes) {
visitedNodes.push(start)
for (currentNode in start.nodes) {
val dist = search(currentNode, nodeB, cumulativePathWeight + weight(nodeA, currentNode), visitedNodes)
minDist = Math.min(dist, minDist)
}
visitedNodes.pop()
}
return minDist
}The graph in the above code uses the adjacency list representation where each node has a list attribute containing references to its neighbors. Another form of representation is the adjacency matrix where the indices represent the node IDs and the value is the associated weight.
In order to store the actual path, we modify the above algorithm to return a copy of the visited nodes.
Below is a pseudocode for finding the shortest path and returning its nodes:
fun shortestPath(start: Node, nodeB: Node, cumulativePathWeights: Int, visitedNodes: Stack<Node>): Pair<Stack<Node>?, Int> {
if (start == nodeB) {
val path = Stack<Node>(path) // Copy the current path
path.push(nodeB)
return pairOf(path, cumulativePathWeights)
}
var minDist = Int.MAX_VALUE
var bestPath: Stack<Node>? = null
if (start !in visitedNodes) {
visitedNodes.push(start)
for (currentNode in start.nodes) {
val (path, dist) = search(currentNode, nodeB, cumulativePathWeight + weight(nodeA, currentNode), visitedNodes)
if (dist < minDist) {
minDist = dist
bestPath = path
}
}
visitedNodes.pop()
}
return pairOf(bestPath, minDist)
}Dijkstra's algorithm
Dijkstra's algorithm finds the shortest distances between a starting node and all the other nodes in the graph. It does this by creating a distance array with a size equal to the number of nodes in the graph. The entries in this array are set to ∞ except at the index of the source node where its value is set to zero.
The core idea of the Dijkstra's algorithm is to use a min-heap where the top of the heap always contains the node which has the shortest distance from the source. When visiting the current node's neighbors, the algorithm updates the distance array if the newly found path is shorter than the existing one.
The code below is an implementation of the Dijkstra's algorithm for a graph following the adjacency matrix representation:
fun dijkstraAlgorithm(graph: Array<Array<Int>>, sourceVertexId: Int): Array<Int> {
// Initially we assume all the vertices, except the source one, are unreachable.
val distances = Array(graph.size) { Int.MAX_VALUE }
distances[sourceVertexId] = 0
// PriorityQueue is a heap tree which returns the next node with the shortest path from the root
val queue = PriorityQueue<Int> { o1, o2 -> distances[o1].compareTo(distances[o2]) }
queue.add(sourceVertexId)
// We use a set to keep track of the visited nodes, so we don't visit them again and loop indefinitely
val visitedVertices = mutableSetOf<Int>()
while (queue.isNotEmpty()) {
val vertexId = queue.poll()
if (vertexId !in visitedVertices) {
visitedVertices.add(vertexId)
getNeighbors(vertexId, graph)
.forEach {
// Update the distance for the current node if a shorter path was found
if (distances[vertexId] + graph[vertexId][it] < distances[it]) {
distances[it] = distances[vertexId] + graph[vertexId][it]
}
queue.add(it)
}
}
}
return distances
}To keep track of the actual paths from the source node to every other node in the graph, we use an integer array to map the node index to the index of the node that precedes it along the shortest path.
data class Path(val weight: Int, val vertices: Array<Int>)
fun dijkstraAlgorithm(graph: Array<Array<Int>>, sourceVertexId: Int): Array<Path> {
val distances = Array(graph.size) { Int.MAX_VALUE }
distances[sourceVertexId] = 0
val queue = PriorityQueue<Int> { o1, o2 -> distances[o1].compareTo(distances[o2]) }
queue.add(sourceVertexId)
val visitedVertices = LinkedList<Int>()
val nodeHops = Array(graph.size) { -1 }
while (queue.isNotEmpty()) {
val vertexId = queue.poll()
if (vertexId !in visitedVertices) {
visitedVertices.add(vertexId)
getNeighbors(vertexId, graph)
.forEach {
if (distances[vertexId] + graph[vertexId][it] < distances[it]) {
distances[it] = distances[vertexId] + graph[vertexId][it]
nodeHops[it] = vertexId
}
queue.add(it)
}
}
}
return distances.indices.map {
var currentIndex = it
val path = mutableListOf<Int>()
while (nodeHops[currentIndex] != -1) {
path.add(currentIndex)
currentIndex = nodeHops[currentIndex]
}
path.add(currentIndex)
path.reverse()
Path(distances[it], path.toTypedArray())
}.toTypedArray()
}Conclusion
Hopefully by now, you have a better understanding of how to solve problems about finding the shortest path. You may not need to use these two algorithms in your day to day job or even implement them yourself, but the ideas behind them can always be useful in other areas of programming. For example: using a set to avoid cycling in a graph or the use of min-heap in the Dijkstra's algorithm.