Dijkstra's algorithm is a popular search algorithm used to determine the shortest path between two nodes in a graph. There are many examples of the algorithm on the web. If you don't like Dijkstra's algorithm, modify it or create your own. (Chewing on this problem is a great learning experience.)

*A small node-and-cost diagram (graph)*

- cost could represent anything: travel time, travel distance, fuel use, congestion, pollution, ...
- -1 indicates no direct node to node connection
- using this matrix, from->to and to->from costs can be different
- To find the cost between node A -> B
- pick a start node - column (node A)
- pick an end node - row (node B)
- find cost at matrix [row][column] i.e. [from-node][to-node]

- this matrix is used to create the minimum cost paths between nodes

# ---- node to node cost --------------------------------------
#
# [0] [1] [2] [3] [4] [5] (col is from-node)
#
costs = [ [ 0, 4, -1, -1, 2, 8 ], # row is to-node [0]
[ 4, 0, 10, -1, 6, -1 ], # row is to-node [1]
[ -1, 10, 0, 3, -1, -1 ], # row is to-node [2]
[ -1, -1, 3, 0, 4, 5 ], # row is to-node [3]
[ 2, 6, -1, 4, 0, -1 ], # row is to-node [4]
[ 8, -1, -1, 5, -1, 0 ] ] # row is to-node [5]

# ---- accumulated minimum path costs -------------------------
#
# [0] [1] [2] [3] [4] [5] (col is from-node)
#
accumulated_costs = [ [ 0, 4, 9, 6, 2, 8 ], # row is to-node [0]
[ 4, 0, 10, 10, 6, 12 ], # row is to-node [1]
[ 9, 10, 0, 3, 7, 8 ], # row is to-node [2]
[ 6, 10, 3, 0, 4, 5 ], # row is to-node [3]
[ 2, 6, 7, 4, 0, 9 ], # row is to-node [4]
[ 8, 12, 8, 5, 9, 0 ] ] # row is to-node [5]

- pick a start node (from-node/column) and an end node (to-node/row)
- a value of -1 indicate the to-node and from-node are the same node
- in the to-node row, the value at [row,column] is the next node (column) in the minimum path from start node to end node
- for example:
- the minimum path from node 3 to node 1 is
**3 -> 4 -> 1** - the minimum path from node 2 to node 0 is
**2 -> 3 -> 4 -> 0**

- the minimum path from node 3 to node 1 is

# ---- minimum paths ------------------------------------------
#
# [0] [1] [2] [3] [4] [5] (col is from-node)
#
min_path = [ [ -1, 0, 3, 4, 0, 0 ], # row is to-node [0]
[ 1, -1, 1, 4, 1, 0 ], # row is to-node [1]
[ 4, 2, -1, 2, 3, 3 ], # row is to-node [2]
[ 4, 4, 3, -1, 3, 3 ], # row is to-node [3]
[ 1, 4, 3, 4, -1, 3 ], # row is to-node [4]
[ 5, 0, 3, 5, 3, -1 ] ] # row is to-node [5]

Click HERE for more information.

I use it because it is simpler to use and easier to modify. And, you only have to work with outbound nodes when designing a new cost matrix. (It can also be easily converted to a regular 2D cost matrix.

Python Program for Dijkstra's shortest path algorithm

Dijkstra's shortest path algorithm

A self learnerâ€™s guide to shortest path algorithms, with implementations in Python

Dijkstra's Algorithm

Dijkstra Algorithm in Python

Implementing Djikstra's Shortest Path Algorithm with Python

A* Pathfinding Visualization Tutorial - Python A* Path Finding Tutorial
(YouTube)

How Dijkstra's Algorithm Works
(YouTube)