In today's age, we all know how important computers have become. Whether we realize or not, nearly every little thing we use nowadays contains some sort of computer in it. And if it wasn't for their ability to "talk" to each other, they wouldn't have had nearly as important as a role in improving the quality of our lives.
As an exercise for your imagination, just think how far we as humans would've got if we couldn't speak to one another. Not that far, right?
Context
The old shortest-path question, "one of the most well-studied combinatorial optimization problems"[1], seems to still not have a definitive answer even today, as developers keep coming up with solutions through which they solve the problem just a little bit quicker with every new iteration.
As an answer to this classic problem, computer scientist Edsger W. Dijkstra built his well-known algorithm in 1956, three years before actually publishing it[2]. Since then, it has been used in many applications, and it serves as a basis for more specialized algorithm variants.
Link State Routing
One of the things at the base of which stays Dijkstra's algorithm is part of the backbone of the modern Internet: link-state routing[3].
Link State Routing is an algorithm found in the Network layer of the OSI Model[4]. It is used by routers - nodes in a network - to determine the shortest valid path that they can use to send a packet to the intended destination, and requires that each router maintains a full overview of the network. IS-IS and OSPF are two variants of link state routing that are mainly used by the Internet (and other large networks) today[3].
By and large, link state routing consists of the following steps:
Link State Routing Recipe
1. Pour 3 cups of flour, one cup of milk, and crack 2 eggs together in a bowl and whisk thoroughly-
Ah, wrong recipe. Sorry!
Actual Link State Routing Recipe
1. All routers send packets with information about their direct neighbors throughout the network;
2. The packets that are sent are said to "flood" the network (that means they will go through every router that exists in the network);
3. Upon receiving all the packets sent over the network, routers go on by building an overview of it...
...and voila! Upon obtaining the network overview, routers can now run (usually a variant of) Dijkstra's algorithm to find out the fastest route to each node within said network[3].
Quite a long context if you ask me, now let's get to the actual main point of this article!
Dijkstra's Algorithm
The algorithm is fairly simple to grasp, contrary to what some may believe. Nevertheless, it is very important to know how Dijkstra's algorithm works for a thorough understanding of computer networks, as it's one of the building blocks of them (once again).
The algorithm is basically a result of applying the greedy method design pattern to the problem of finding the shortest path[6].
Greedy method: building up a solution iteratively (from pieces) by choosing the most obvious and immediate option every time (the best option for that specific iteration, every iteration)[5].
But what does that mean exactly?
The Algorithm
fig. 1
Let's look at this graph, for instance. Say we want to get from A to Z. But what path should we take such that we get the smallest possible cost? How would we approach this issue?
1. We firstly give each node an initial value. We give A the value 0 (since that's where we're starting) and infinity (noted with "inf") to everything else (fig. 2). Doing this gives us a nice order of going through the nodes: we will always visit the node with the smallest assigned number first.
fig. 2 - the value assigned to each node will represent the cost of getting to that node from the starting point upon completing the algorithm
2. Now let's start with the actual pathfinding. We choose the node with the smallest value - that's A - and we visit each of its neighbors while taking the weight of the connecting edge and A's assigned number into account. Upon visiting each neighbor, what we do is pretty much ask ourselves: "is the weight of this edge + A's number less than whatever number is assigned to our neighbor? If yes, replace it with this new sum" (fig. 3).
fig. 3
3. Now that was A. We select the next node by comparing the values of the nodes we haven't visited yet and choosing the one with the smallest value, in our case B. We keep doing these two steps until we have visited every node of the graph (fig. 4).
We do the same for nodes D and Z. Eventually, we will get to:
fig. 4
Eventually, we get a path from A to Z that yields the smallest cost out of all the possible paths within the graph: 8. And that was Dijkstra's in a nutshell!
You can go on this link[8] if you'd like to see some more examples (and even make them yourself!) of Dijkstra's algorithm.
That being said, we make some observations:
- The solution we get is not necessarily the shortest path with regard to the number of edges used;
- There may be other solutions too that have the total cost of 8; It's just that those will never get chosen using the greedy approach because they are not a series of best immediate options - the algorithm cannot "see forward" in order to get a good global solution: it will never choose a more expensive immediate option, even if that would mean getting a cheaper/the same final solution.
- The resulting graph will always represent a tree;
- Dijkstra's algorithm does not work on graphs that have edges with negative weights. For those, we'll need to implement the Bellman-Ford algorithm, but this is a story for another time;
- The implementation you'll see below only works on undirected graphs, although it can be modified to work for directed ones too;
- Technically the algorithm presented here only yields the smallest costs of getting to each node in the graph from a starting point (that is, the numbers assigned to each node), and not the paths themselves too[6]! In order to also get the resulting tree (i.e. the one we see in the last image for our example), we'll have to make a small adjustment that you will see later.
All code snippets provided will be using Java. You can easily find equivalent implementations in other programming languages by searching online.
Java Implementation
For representing the graph, we will be using a bi-dimensional array, as it's the easiest data structure to grasp out of them all(i). For the graph we saw earlier, the table will look like this:
fig. 5
int[][] graph = new int[][] {
{0, 1, 3, 0, 0},
{1, 0, 2, 5, 7},
{3, 2, 0, 10, 6},
{0, 5, 10, 0, 10},
{0, 7, 6, 10, 0}
};
Note that we can optimize it a little bit by only using one of the "triangles" on either side of the main diagonal, but that's besides the point for now.
/**
* Returns the unvisited node that currently holds
* the smallest value in the array "distances[]".
*/
private static int getMinDistanceNode(int[] distances,
boolean[] visited) {
int minValue = Integer.MAX_VALUE, nodeIndex = -1;
for (int i = 0; i < distances.length; i++) {
if (distances[i] < minValue && !visited[i]) {
minValue = distances[i];
nodeIndex = i;
}
}
return nodeIndex;
}
Before getting to the main part, we declare a helper method named getMinDistanceNode() which goes through the values held by each node in the graph and returns the one with the smallest value that has not yet been visited. If all nodes have already been visited (so visited[] contains only trues), the method simply returns -1, which we will designate as "no valid node".
Now let's begin calculating the distances through Dijkstra.
/**
* Perform Dijkstra's algorithm on a given graph,
* starting from node "startNode".
*/
private static int[] dijkstra(int[][] graph, int startNode) {
int currentNode, vertexCount = graph.length;
int[] distances = new int[vertexCount];
boolean[] visited = new boolean[vertexCount];
distances[startNode] = 0;
for (int i = 1; i < distances.length; i++)
if (i != startNode)
distances[i] = Integer.MAX_VALUE;
currentNode = startNode;
// While we still have unvisited nodes
while (currentNode != -1) {
for (int i = 0; i < vertexCount; i++) {
if (graph[currentNode][i] != 0
&& graph[currentNode][i] + distances[currentNode] < distances[i])
distances[i] = graph[currentNode][i]
+ distances[currentNode];
}
visited[currentNode] = true;
currentNode = getMinDistanceNode(distances, visited);
}
return distances;
}
Firstly, we declare:
-
currentNodefor pointing to each node in the graph; -
vertexCountas the number of nodes; -
distancesas the array that will contain the (eventually shortest) costs of getting to each node that we will return upon executing the algorithm; -
visitedas an array of bools through which we keep count of what nodes we have already visited.
After that, we set the distance from the starting node to itself to 0 (duh) while setting all the other distances to "infinity" (actually just a really big number), following that they will get "relaxed" upon finding shorter paths.
We set currentNode to point to our starting node.
Then, as long as the method getMinDistanceNode returns a valid node index (so not -1), for each neighbor of the node we're currently pointing at we update its value in the array distances with the sum of the current node's value and the distance from it to the neighbor (distances[currentNode] + graph[currentNode][i]) if this sum is smaller than the neighbor's current value and if the two nodes are actually neighbors, i.e. there's an edge between them with weight > 0. After we are done with that, we mark our currently selected node as "visited" and choose another one. Repeat for the rest of the nodes in the matrix.
fig. 6 - traversing the adjacency matrix in the dijkstra method
Once all nodes have been visited, we are left with an array which holds the smallest cost of getting to each node in the graph from the specified starting point, array which we can finally return.
We can test our algorithm by running it against our example:
public static void main(String[] args) {
int[][] graph = new int[][] {
{0, 1, 3, 0, 0},
{1, 0, 2, 5, 7},
{3, 2, 0, 10, 6},
{0, 5, 10, 0, 10},
{0, 7, 6, 10, 0}
};
// 0 stands for node A in our example, Z is index 4
int[] res = dijkstra(graph, 0);
for (int no : res) System.out.print(no + " ");
}
...and as expected, it returns an array holding the values [0, 1, 3, 6, 8].
The complete program:
public class Main {
/*
* We will denote two vertices not having an
* edge between them with 0.
*/
public static void main(String[] args) {
int[][] graph = new int[][] {
{0, 1, 3, 0, 0},
{1, 0, 2, 5, 7},
{3, 2, 0, 10, 6},
{0, 5, 10, 0, 10},
{0, 7, 6, 10, 0}
};
int[] res = dijkstra(graph,0);
for (int no : res) System.out.println(no);
}
private static int[] dijkstra(int[][] graph, int startNode) {
int currentNode, vertexCount = graph.length;
int[] distances = new int[vertexCount];
boolean[] visited = new boolean[vertexCount];
distances[startNode] = 0;
for (int i = 1; i < distances.length; i++)
if (i != startNode)
distances[i] = Integer.MAX_VALUE;
currentNode = startNode;
visited[startNode] = true;
// While we still have unvisited nodes
while (currentNode != -1) {
for (int i = 0; i < vertexCount; i++) {
if (graph[currentNode][i] != 0
&& graph[currentNode][i] + distances[currentNode] < distances[i])
distances[i] = graph[currentNode][i]
+ distances[currentNode];
}
visited[currentNode] = true;
currentNode = getMinDistanceNode(distances, visited);
}
return distances;
}
/**
* Returns the unvisited node that currently holds
* the smallest value in the array "distances[]".
*/
private static int getMinDistanceNode(int[] distances,
boolean[] visited) {
int minValue = Integer.MAX_VALUE, nodeIndex = -1;
for (int i = 0; i < distances.length; i++) {
if (distances[i] < minValue && !visited[i]) {
minValue = distances[i];
nodeIndex = i;
}
}
return nodeIndex;
}
}
Follow-up
Of course, we'll still have to make that adjustment I talked to you about if we also want to get the resulting tree. That will be coming soon in another post, so stay tuned!
Conclusion
That was all there is for the basics of Dijkstra's algorithm, a simple, yet elegant way of solving the classic shortest path problem. Despite having been around for quite some time now, it's still being widely used as a means of assuring efficient communications between the various devices in a network.
What do you think about Dijkstra's algorithm? What about this post? Or maybe you have something interesting on the topic to share with others. I'm definitely looking forward to hearing your thoughts below!
Notes
i. For a more elaborate list on what data structures one can use to represent a graph, you can check out the chapter "Data Structures for Graphs" from the book Data Structures and Algorithms in Java™[7].
References
- Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E., "Faster algorithms for the shortest path problem", Journal of the ACM 37 (2):213-223, doi: 10.1145/77600.77615.
- "Dijkstra's algorithm", Wikipedia, https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
- Andrew S. Tanenbaum; David J. Wetherall, "Link State Routing", in Comptuer Networks, 5th ed., Pearson, 2010, 373-378, ISBN: 978-0132126953.
- Mahmud Hasan; EdXD, "What is the OSI Model – 7 Layers of OSI Model Explained", ByteXD, https://bytexd.com/osi-model/.
- "Greedy Algorithms", GeeksforGeeks, https://www.geeksforgeeks.org/greedy-algorithms/.
- Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser, "Dijkstra's Algorithm", in Data Structures and Algorithms in Java™, 6th ed., John Wiley & Sons, 2014, 653-661, ISBN: 978-1-118-77133-4.
- Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser, "Data Structures for Graphs", in Data Structures and Algorithms in Java™, 6th ed., John Wiley & Sons, 2014, 619-629, ISBN: 978-1-118-77133-4.
- "Single-source shortest paths", Visualgo.net, https://visualgo.net/en/sssp?slide=1.
Top comments (0)