dijkstra

Another single-function implementation of Dijkstra's Algorithm for shorter path finding in a directed matrix-graph

A single-function implementation of Dijkstra's algorithm for shorter path finding in a directed matrix-graph

Didactic reference of Dijkstra's algorithm at: https://youtu.be/bZkzH5x0SKU

% Matrix-Graph example G

% G(a,b)=z defines a directional link with a weight z from (only) the node a to b, use G(b,a)=w to link from the node b to a

G = [;

0 1 0 0 0 0 0;

0 0 1 0 0 10 0;

2 0 0 1 0 0 0;

0 0 2 0 1 0 0;

0 0 0 2 0 1 0;

0 0 0 0 2 0 1;

0 0 0 0 0 2 0;

];

initialNode = 1;

finalNode = 7;

% call the search function

[best_route, cost, M] = dijkstra(G, initialNode, finalNode)

best_route =

1 2 3 4 5 6 7

cost =

6

% Node number | best previous node | cumulative path lenght or cost | node visited in the search

M =

1 0 0 1

2 1 1 1

3 2 2 1

4 3 3 1

5 4 4 1

6 5 5 1

7 6 6 1

% Interpretation of the columns of the Dijkstra matrix M

The interpretation starts on the finalNode (row 7 with 7 6 6 1)

Node 7 reached from the node 6 with a path-length or cost of 6, node visited (so the links defined in the graph G allows the finalNode to be reached from the initialNode)

Node 6 reached from the node 5 with a path-length or cost of 5, node visited

…

Node 2 reached from the node 1 with a path-length or cost of 1, node visited

Node 1 is the initialNode of the search, node visited