dijk {gor} | R Documentation |
Dijkstra' algorithm for shortest paths
Description
Dijkstra's algorithm finding the sorthest paths from a root vertex to the remaining vertices of a graph using a spanning tree
Usage
dijk(g, d, r = 1)
Arguments
g |
An igraph Graph |
d |
Weights (lengths) of the edges of |
r |
Starting vertex — root of the output tree |
Details
An implementation of Dijkstra's algorithm.
Value
A list with components: $tree, which is a sequence of
pairs of vertices parent-son; $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.
Author(s)
Cesar Asensio
See Also
shortest_paths in the 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
gTd <- make_graph(Td$tree, n = gorder(g)) # igraph tree
Eg <- as_edgelist(g)
dl <- c() # We convert the matrix in a list:
for (e in 1:nrow(Eg)) { dl <- c(dl, d[Eg[e,1], Eg[e,2]]) }
z <- layout_with_kk(g)
plot(g, layout = z, edge.label = dl)
plot(gTd, layout = z, edge.color = "red3", add = TRUE)
[Package gor version 1.0 Index]