gor (version 2.0)

dijk: Dijkstra' algorithm for shortest paths

Description

Dijkstra's algorithm finding the shortest paths from a root vertex to the remaining vertices of a graph using a spanning tree

Usage

dijk(
  g,
  d,
  r = 1,
  plot.steps = FALSE,
  color = c("navajowhite", "orangered3", "black", "white", "cyan4"),
  pause = 2,
  pdf = FALSE,
  ...
)

Value

A list with components: $tree, which is the spanning tree leading to minimum distances with r as root in igraph format; $distances, which is a \(2\times n\) matrix with distances from the root vertex to the remaining vertices, and $parents, which contains the parent of each vertex in the tree, except for the root which has no parent, so its entry is NA.

Arguments

g

An igraph graph.

d

Weights (lengths) of the edges of \(g\). It should be given as a \(n\times n\) symmetric distance matrix, with \(n\) being the number of vertices of \(g\). Please note that only the distances corresponding to edges of the graph \(g\) will be taken into account.

r

Starting vertex --- root of the output tree. It defaults to 1.

plot.steps

Boolean indicating whether the routine should plot the intermediate steps of the algorithm to see the growing of the tree into the minimum distance spanning tree. It defaults to FALSE.

color

A set of colors to mark the vertices, vertex labels and edges added to the tree as it grows, see details below. It is only used when plot.steps is set to TRUE.

pause

Time interval (in seconds) between successive steps of the algorithm. It is only used when plot.steps is set to TRUE and it defaults to 2.

pdf

Boolean indicating whether the routine should eject pdf plots of intermediate steps of the algorithm, see details below. It is only used when plot.steps is set to TRUE and it defaults to FALSE.

...

Further parameters to pass to the plotting routine, especially the layout parameter.

Author

Cesar Asensio

Details

An implementation of Dijkstra's algorithm. Is is an exact algorithm to find the shortest path from a given (root) vertex to each vertex of a given weighted graph. The shortest paths form a spanning tree, and the distances from the root to the remaining vertices are computed as sums of the weights of the edges in each path. Please note that the minimum may not be unique, and different solutions can be found by changing the visiting order of neighbors when some distances coincide.

This routine can plot the algorithm stepwise for illustrative purposes. To do that, set the parameter "plot.steps" to TRUE and adjust the "pause" parameter to some convenient value if desired (its default value is 2). The "color" parameter, a list of five R colors, is used to color the vertices and vertex labels of the graph, as well as the edges of the spanning tree: The first (third) color marks the vertices (vertex labels) outside the growing tree and the second (fourth) those inside it. The fifth color marks the edges forming the growing tree. The default value of the "color" parameter is c("navajowhite", "orangered3", "black", "white", "cyan4"). Finally, by setting the "pdf" parameter to TRUE, this routine can also output the individual plots as a bunch of pdf files which can be included in a LaTeX animation.

See Also

igraph::shortest_paths() in the igraph::igraph package.

Examples

library(igraph)
g <- make_graph("Frucht")
n <- gorder(g)
set.seed(1)
d <- matrix(round(runif(n^2, min = 1, max = 10)), nrow = n)  # Distances
d <- d + t(d); for (i in 1:n) { d[i,i] <- 0 }          # Distance matrix
Td <- dijk(g, d, r = 1)
Td$distances
Td$parents
## To plot the result:
## z <- layout_with_gem(g)
## T <- dijk(g, d, r = 1, plot.steps = TRUE, layout = z)