EVOLUTION-MANAGER
Edit File: shortestPaths.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: Find Shortest Paths Between All Nodes in a Directed Graph</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <link rel="stylesheet" type="text/css" href="R.css" /> </head><body> <table width="100%" summary="page for allShortestPaths {e1071}"><tr><td>allShortestPaths {e1071}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Find Shortest Paths Between All Nodes in a Directed Graph</h2> <h3>Description</h3> <p><code>allShortestPaths</code> finds all shortest paths in a directed (or undirected) graph using Floyd's algorithm. <code>extractPath</code> can be used to actually extract the path between a given pair of nodes. </p> <h3>Usage</h3> <pre> allShortestPaths(x) extractPath(obj, start, end) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>x</code></td> <td> <p>matrix or distance object</p> </td></tr> <tr valign="top"><td><code>obj</code></td> <td> <p>return value of <code>allShortestPaths</code></p> </td></tr> <tr valign="top"><td><code>start</code></td> <td> <p>integer, starting point of path</p> </td></tr> <tr valign="top"><td><code>end</code></td> <td> <p>integer, end point of path</p> </td></tr> </table> <h3>Details</h3> <p>If <code>x</code> is a matrix, then <code>x[i,j]</code> has to be the length of the direct path from point <code>i</code> to point <code>j</code>. If no direct connection from point <code>i</code> to point <code>j</code> exist, then <code>x[i,j]</code> should be either <code>NA</code> or <code>Inf</code>. Note that the graph can be directed, hence <code>x[i,j]</code> need not be the same as <code>x[j,i]</code>. The main diagonal of <code>x</code> is ignored. Alternatively, <code>x</code> can be a distance object as returned by <code><a href="../../stats/html/dist.html">dist</a></code> (corresponding to an undirected graph). </p> <h3>Value</h3> <p><code>allShortestPaths</code> returns a list with components </p> <table summary="R valueblock"> <tr valign="top"><td><code>length</code></td> <td> <p>A matrix with the total lengths of the shortest path between each pair of points.</p> </td></tr> <tr valign="top"><td><code>middlePoints</code></td> <td> <p>A matrix giving a point in the middle of each shortest path (or 0 if the direct connection is the shortest path), this is mainly used as input for <code>extractPath</code>.</p> </td></tr> </table> <p><code>extractPath</code> returns a vector of node numbers giving with the shortest path between two points. </p> <h3>Author(s)</h3> <p>Friedrich Leisch</p> <h3>References</h3> <p>Kumar, V., Grama, A., Gupta, A. and Karypis, G. Introduction to Parallel Programming - Design and Analysis of Algorithms, Benjamin Cummings Publishing, 1994, ISBN 0-8053-3170-0</p> <h3>Examples</h3> <pre> ## build a graph with 5 nodes x <- matrix(NA, 5, 5) diag(x) <- 0 x[1,2] <- 30; x[1,3] <- 10 x[2,4] <- 70; x[2,5] <- 40 x[3,4] <- 50; x[3,5] <- 20 x[4,5] <- 60 x[5,4] <- 10 print(x) ## compute all path lengths z <- allShortestPaths(x) print(z) ## the following should give 1 -> 3 -> 5 -> 4 extractPath(z, 1, 4) </pre> <hr /><div style="text-align: center;">[Package <em>e1071</em> version 1.7-3 <a href="00Index.html">Index</a>]</div> </body></html>