dijk {gor}

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 g

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)