dijkstra

Versión 1.01 (2,32 KB) por
Another single-function implementation of Dijkstra's Algorithm for shorter path finding in a directed matrix-graph
57 descargas

Ver licencia

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

Citar como

Jordi Palacin (2024). dijkstra (https://www.mathworks.com/matlabcentral/fileexchange/134851-dijkstra), MATLAB Central File Exchange. Recuperado .

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

Compatibilidad con la versión de MATLAB
Se creó con R2015b
Compatible con cualquier versión
Windows macOS Linux