Shortest path

The shortest path in graph theory identifies the path across the nodes of a graph with the lowest cost to go from an origin to a destination. A classic real-life example could is a map routing application where the user wants to go from point A to point B as quickly as possible, minimizing the total weights during the path.

Depending on the type of graph (undirected, directed, mixed, and so on), different algorithms apply. In our case, we are going to study the Dijkstra algorithm. For Dijkstra, we are going to deal with a directed non-negative weight graph.