Published in

basecs

# Graphs that weigh heavy on your mind

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.

# Rules of Dijkstra’s game

1. Every time that we set out to visit a new node, we will choose the node with the smallest known distance/cost to visit first.
2. Once we’ve moved to the node we’re going to visit, we will check each of its neighboring nodes.
3. 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.
4. 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.

# Resources

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

--

--

## More from basecs

Exploring the basics of computer science, every Monday, for a year.

## Get the Medium app

Writing words, writing code. Sometimes doing both at once.