Description Usage Arguments Details Value Examples
View source: R/FloydWarshall.R
Use the Floyd-Warshall algorithm to calculate the shortest path between all pairs of vertices in a directed, weighted graph.
1 | floydWarshall(graph)
|
graph |
The |
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.
An spresults
object.
1 2 3 4 5 6 7 8 9 | g <- randomGraph(6,euclidean=FALSE)
fw <- floydWarshall(g)
plot(fw)
for(step in fw){
print(step$min_dists)
}
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.