floydWarshall: Floyd-Warshall Algorithm

In mhils/shortestpath: Shortest Path Algorithm Visualization

Description

Use the Floyd-Warshall algorithm to calculate the shortest path between all pairs of vertices in a directed, weighted graph.

Usage

floydWarshall(graph)

Arguments

graph

The igraph object.

Details

The Floyd-Warshall algorithm is a multi-source algorithm which can (in contrast to Dijkstra and A*-Search) deal with negative edge weights. Note that in order to find the right shortest path, it is required that no negative-weight cycle exist in the graph. The algorithm automatically detects negative-weight cycles and shows a corresponding error message.

The algorithm updates the minimal distance of each vertex pair #V number of times. Thus, the running time complexity of the algorithm is #V^3.

Caveat: The computation of the distances is based on an adjacency matrix. A limitation in igraph mandates that an edge weight of zero indicates that there exist no edge between two vertices.

Value

An spresults object.

Examples

g <- randomGraph(6,euclidean=FALSE)

fw <- floydWarshall(g)

plot(fw)

for(step in fw){
   print(step$min_dists)
}

mhils/shortestpath documentation built on Dec. 17, 2020, 3:19 p.m.