dijkstra
Version 1.01 (2.32 KB) by
Jordi Palacin
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
Cite As
Jordi Palacin (2024). dijkstra (https://www.mathworks.com/matlabcentral/fileexchange/134851-dijkstra), MATLAB Central File Exchange. Retrieved .
Used in: Path Planning of a Mobile Delivery Robot Operating in a Multi-Story Building Based on a Predefined Navigation Tree. Sensors 2023, 23, 8795. https://doi.org/10.3390/s23218795
MATLAB Release Compatibility
Created with
R2015b
Compatible with any release
Platform Compatibility
Windows macOS LinuxTags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.