Menu
I know that R is statistical pkg, but probably there is library to work with graphs and find shortest path btw 2 nodes.
PS actually, I've found igraph and e1071, which one is better? Thank you
805
Dijkstra's algorithm can be used to determine the shortest path from one node in a graph to every other node within the same graph data structure, provided that the nodes are reachable from the starting node. Dijkstra's algorithm can be used to find the shortest path.
Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and all other nodes in a graph. This algorithm uses the weights of the edges to find the path that minimizes the total distance (weight) between the source node and all other nodes.
We say that BFS is the algorithm to use if we want to find the shortest path in an undirected, unweighted graph. The claim for BFS is that the first time a node is discovered during the traversal, that distance from the source would give us the shortest path. The same cannot be said for a weighted graph.
The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.
Sure, there's a Task View that gathers a fair number of the graph-related Packages. (The page linked to is a CRAN portal, which uses iframes, so i can't directly link to the Graph Task View. So from the page linked to here, click on Task Views near the top of the LHS column, then click on the Task View gR, near the bottom of the list.
Among the Packages there, igraph, for instance, has graph-theoretic functions such as you have mentioned in your Q.
igraph versus e1071--well, igraph is coded in C; it's very fast. I have not compared it with e1071 though.
What i do know is that these two packages differ a great deal in scope: e1071 is a collection of functions (at least originally) for a University course (i believe the unusual name 'e1071' refers to the course identifier), while. e1071 indeed contains a graph theoretic functions, but the majority of the Package's functions are directed to machine learning.
iGraph on the other hand is a dedicated graph theoretic Package. iGraph has many more dedicated functions, as well as constructors for a number of common graph types.
64
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
