k-Shortest Paths

This document will show, how to find k-shortest paths in a graph using igraph library. Typical example can be finding route between two places and wanting to have several alternatives to choose from.

The procedure will be similar to the one used by Yen's algorithm. The idea is following:

• Assume, we have shortest path between two nodes in a graph
• Iterate through edges of shortest path, removing one of them each iteration, and calculating shortest path - alternative routes
• Shortest of alternative routes is second shortest path
• Shortest path n will be shortest alternaive route to shortest paths n-1, n-2, …, 1

Implementation in R is following:

# find k shortest paths
k.shortest.paths <- function(graph, from, to, k){
  # first shortest path
  k0 <- get.shortest.paths(graph,from,to, output='both')

  # number of currently found shortest paths
  kk <- 1

  # list of alternatives
  variants <- list()

  # shortest variants
  shortest.variants <- list(list(g=graph, path=k0$epath, vert=k0$vpath, dist=shortest.paths(graph,from,to)))

  # until k shortest paths are found
  while(kk<k){
    # take last found shortest path
    last.variant <- shortest.variants[[length(shortest.variants)]]              

    # calculate all alternatives
    variants <- calculate.variants(variants, last.variant, from, to)

    # find shortest alternative
    sp <- select.shortest.path(variants)

    # add to list, increase kk, remove shortest path from list of alternatives
    shortest.variants[[length(shortest.variants)+1]] <- list(g=variants[[sp]]$g, path=variants[[sp]]$variants$path, vert=variants[[sp]]$variants$vert, dist=variants[[sp]]$variants$dist)
    kk <- kk+1
    variants <- variants[-sp]
  }

  return(shortest.variants)
}

# found all alternative routes
calculate.variants <- function(variants, variant, from, to){
  # take graph from current path
  g <- variant$g

  # iterate through edges, removing one each iterations
  for (j in unlist(variant$path)){
    newgraph <- delete.edges(g, j) # remove adge
    sp <- get.shortest.paths(newgraph,from,to, output='both') # calculate shortest path
    spd <- shortest.paths(newgraph,from,to) # calculate length
    if (spd != Inf){ # the the path is found
      if (!contains.path(variants, sp$vpath)) # add to list, unless it already contains the same path
      {
        variants[[length(variants)+1]] <- list(g=newgraph, variants=list(path=sp$epath, vert=sp$vpath, dist=spd))
      }
    }
  }

  return(variants)
}

# does a list contain this path?
contains.path <- function(variants, variant){
  return( any( unlist( lapply( variants, function(x){ identical(x$variant$vert,variant) } ) ) ) )
}

# which path from the list is the shortest?
select.shortest.path <- function(variants){
  return( which.min( unlist( lapply( variants, function(x){x$variants$dist} ) ) ) )
}

And lets see some examples:

(warnings tell me, that removing some edges leads to graph, where the two nodes can not be reached)

library(igraph)

## Warning: package 'igraph' was built under R version 3.0.1

g <- read.graph("graph.gml", format = "graphml")

k.shortest.paths(g, from = 2795, to = 2839, k = 5)

## Warning: At structural_properties.c:5296 :Couldn't reach some vertices
## Warning: At structural_properties.c:5296 :Couldn't reach some vertices
## Warning: At structural_properties.c:5296 :Couldn't reach some vertices

## [[1]]
## [[1]]$g
## IGRAPH U-W- 18452 16415 -- 
## + attr: id (v/c), weight (e/n)
## 
## [[1]]$path
## [[1]]$path[[1]]
## [1] 16
## 
## 
## [[1]]$vert
## [[1]]$vert[[1]]
## [1] 2795 2839
## 
## 
## [[1]]$dist
##      [,1]
## [1,] 81.1
## 
## 
## [[2]]
## [[2]]$g
## IGRAPH U-W- 18452 16414 -- 
## + attr: id (v/c), weight (e/n)
## 
## [[2]]$path
## [[2]]$path[[1]]
##  [1] 4383 4385 4395 4394 4400 3720 3722 3837 3839   14
## 
## 
## [[2]]$vert
## [[2]]$vert[[1]]
##  [1] 2795 2796 2802 2801 2804 2875 1222 1322 1323 1467 2839
## 
## 
## [[2]]$dist
##      [,1]
## [1,] 3930
## 
## 
## [[3]]
## [[3]]$g
## IGRAPH U-W- 18452 16413 -- 
## + attr: id (v/c), weight (e/n)
## 
## [[3]]$path
## [[3]]$path[[1]]
##  [1] 4383 4385 4394 4392 4393 4399 3720 3722 3837 3839   14
## 
## 
## [[3]]$vert
## [[3]]$vert[[1]]
##  [1] 2795 2796 2802 2801 2800 2804 2875 1222 1322 1323 1467 2839
## 
## 
## [[3]]$dist
##      [,1]
## [1,] 3967
## 
## 
## [[4]]
## [[4]]$g
## IGRAPH U-W- 18452 16412 -- 
## + attr: id (v/c), weight (e/n)
## 
## [[4]]$path
## [[4]]$path[[1]]
##  [1] 4383 4385 4393 4392 4390 4391 4397 4398 3720 3722 3837 3839   14
## 
## 
## [[4]]$vert
## [[4]]$vert[[1]]
##  [1] 2795 2796 2802 2801 2800 2798 2805 2804 2875 1222 1322 1323 1467 2839
## 
## 
## [[4]]$dist
##      [,1]
## [1,] 4214
## 
## 
## [[5]]
## [[5]]$g
## IGRAPH U-W- 18452 16413 -- 
## + attr: id (v/c), weight (e/n)
## 
## [[5]]$path
## [[5]]$path[[1]]
##  [1] 4382 4384 4394 4393 4399 3720 3722 3834 3836 3837 3838   14
## 
## 
## [[5]]$vert
## [[5]]$vert[[1]]
##  [1] 2795 2796 2802 2801 2804 2875 1222 1322 1321 1324 1323 1467 2839
## 
## 
## [[5]]$dist
##      [,1]
## [1,] 4311

Resulting object is a list, each item of the list includes graph, indexes of vertices, indexes of edges and distance. Vertices are the same in every graph, and hence their indexes as well. Edges are different, and therefore indexes of edges can differ.