dijkstra

版本 1.01 (2.3 KB) 作者: Jordi Palacin

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

http://robotica.udl.cat

关注

5.0

(1)

61.0 次下载

更新时间 2024/5/6

查看许可证

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 =

% 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

引用格式

Jordi Palacin (2024). dijkstra (https://www.mathworks.com/matlabcentral/fileexchange/134851-dijkstra), MATLAB Central File Exchange. 检索来源 2024/10/2.

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