Re: [igraph] Shortest path with highest weights

[Tamas Nepusz]

> Dear group,
> kindly I have a graph that got the following edges:
>  6 -> 4 with prob 0.4
>  4 -> 3 with prob 0.2
> 
> 6 -> 7 with prob 0.1
> 7 -> 3 with prob 0.01
> 
> I want to get the shortest path between 6, 3 with the highest probability 
> "prob"
> this I wrote this:
> max(E(G,path=get.shortest.paths(G,6,3)$vpath[[1]])$prob)
> 
> this do not give me the vertices in between, how can I get them? and can
> I multiply probabilities instead of adding ?
get.shortest.paths, get.all.shortest.paths and related functions always look
for the path that has the smallest total weight on the edges. If you have
probabilities and you want to _maximize_ the _product_ of the probabilities,
you need to employ a simple trick: replace each probability with its logarithm
times -1 because additions with the log-probabilities work the same way as
multiplications with the "original" probabilities (and you need the -1
multiplier because you want to maximize the product and get.shortest.paths will
try to minimize them).

Best,
T.