dijkstra, an Octave code which implements the Dijkstra algorithm for finding the minimum distance from a given node of a weighted graph to all the other nodes.
The example graph handled by the program has 6 nodes and 8 links, each with a positive length:
N0--15--N2-100--N3 \ | / \ | / 40 20 10 \ | / \ | / N1 / \ / \ 6 25 / \ / \ N5----8-----N4
Using "Inf" to indicate that there is no link between two nodes, the distance matrix for this graph is:
0 40 15 Inf Inf Inf 40 0 20 10 25 6 15 20 0 100 Inf Inf Inf 10 100 0 Inf Inf Inf 25 Inf Inf 0 8 Inf 6 Inf Inf 8 0
Dijkstra's algorithm efficiently determines the length of the shortest path from node 0 to other nodes as:
From 0 to: 0 1 2 3 4 5 Distance: 0 35 15 45 49 41
The computer code and data files described and made available on this web page are distributed under the MIT license
dijkstra is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version
floyd, an Octave code which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.
toms097, an Octave code which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.