# Graphs that weigh heavy on your mind

Before we can really get into Dijkstra’s super-famous algorithm, we need to pick up a few seeds of important information that we’ll need along the way, first.

finding the shortest path between two nodes becomes much trickier when we have to take into account the weights of the edges that we’re traversing through.

Let’s take a look at an example, and this will start to become more clear. In the simple directed, weighted graph below, we have a graph with three nodes (`a`, `b`, and `c`), with three directed, weighted edges.

# Rules of Dijkstra’s game

Dijkstra’s algorithm is unique for many reasons, which we’ll soon see as we start to understand how it works. But the one that has always come as a slight surprise is the fact that this algorithm isn’t just used to find the shortest path between two specific nodes in a graph data structure. Dijkstra’s algorithm can be used to determine the shortest path from one node in a graph to every other node within the same graph data structure, provided that the nodes are reachable from the starting node.

1. Once we’ve moved to the node we’re going to visit, we will check each of its neighboring nodes.
2. For each neighboring node, we’ll calculate the distance/cost for the neighboring nodes by summing the cost of the edges that lead to the node we’re checking from the starting vertex.
3. Finally, if the distance/cost to a node is less than a known distance, we’ll update the shortest distance that we have on file for that vertex.

# Behind the scenes of Dijkstra’s magic

We’ll continue doing the same steps for each vertex that remains unvisited. The next node we’d check in this graph would be `d`, as it has the shortest distance of the unvisited nodes. Only one of node `d`'s neighbors is unvisited, which is node `e`, so that’s the only one that we’ll need to examine.

# Resources

For better or for worse, Dijkstra’s algorithm is one of the most well-known methods of graph traversal in the world of computer science. The bad news is that sometimes it can feel intimidating to try to understand how it works, since there are so many references to it. The good news is that there are plenty of resources out there — you just need to know which ones to start with! Here are some of my favorites.

1. Dijkstra’s Algorithm, Computerphile
2. Dijkstra’s Shortest Paths Algorithm for Graphs, Sesh Venugopal
3. A Single-Source Shortest Path algorithm for computing shortest path, Professor Ileana Streinu
4. A Note on Two Problems in Connexion with Graphs, E.W. Dijkstra

Written by