Re: [igraph] more detailed information on shortest.paths()

[Gábor Csárdi]

Hi Bob,

please see

http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

http://en.wikipedia.org/wiki/Johnson's_algorithm

Gabor

On Tue, Oct 22, 2013 at 9:41 AM, Bob Pap <address@hidden> wrote:

Dear all,

The function description of shortest.paths() indicates:

 The implemented algorithms are breadth-first search (‘unweighted’), this only works for unweighted graphs; the Dijkstra algorithm (‘dijkstra’), this works for graphs with non-negative edge weights; the Bellman-Ford algorithm (‘bellman-ford’), and Johnson's algorithm (‘"johnson"’). The latter two algorithms work with arbitrary edge weights, but (naturally) only for graphs that don't have a negative cycle.

Short of having access to the referenced book (West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall), would you know a reference to what exactly do the algorithms do? Many thanks.

Kindly,

Bob Pap

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help