Shortest path tree with Dijkstra's algorithm

Description

The spTreeDijkstra function computes the shortest path tree of an undirected or directed graph with Dijkstra's algorithm.

Usage

1
spTreeDijkstra(nodes, arcs, source.node = 1, directed = TRUE)

Arguments

nodes

vector containing the nodes of the graph, identified by a number that goes from 1 to the order of the graph.

arcs

matrix with the list of arcs of the graph. Each row represents one arc. The first two columns contain the two endpoints of each arc and the third column contains their weights.

source.node

number pointing the source node of the graph. It's node 1 by default.

directed

logical value indicating whether the graph is directed (TRUE) or not (FALSE).

Details

Dijkstra's algorithm was developed by the computer scientist Edsger Dijkstra in 1956 and published in 1959. This is an algorithm that can computes a shortest path tree from a given source node to the others nodes that make a connected graph, directed or not, with non-negative weights.

Value

spTreeDijkstra returns a list with:

tree.nodes

vector containing the nodes of the shortest path tree.

tree.arcs

matrix containing the list of arcs of the shortest path tree.

stages

number of stages required.

distances

vector with distances from source to other nodes

References

Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik 1, 269-271.

See Also

A more general function getShortestPathTree.

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.