Shortest Path
Test Matrix Rows/Columns
(need this. sometimes I get lost.)
JSON File Demos
Write Minimum Path JSON File
Read Minimum Path JSON File
Solution Using Code From Web
Random Graph Generation
Random Distribution
Draw Compact Costs Connection Graph
Example From The Web

Introduction

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.)

Several projects can be found HERE .

Simple Cost Matrix

A small node-and-cost diagram (graph)
image missing

# ---- 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]

Resultant Minimum Path Matrix

  1. pick a start node (from-node/column) and an end node (to-node/row)
  2. a value of -1 indicate the to-node and from-node are the same node
  3. 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
  4. 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

# ---- 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]

A More Compact Version of the Cost Matrix

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.

Links

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)