Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
282 views
in Technique[技术] by (71.8m points)

r - Shortest path (path + length) in Igraph

I have a (possibly dumb) shortest path question. What is the best way to get both the path (vpath is perfect for me) and the total weight of the shortest path. I see functions shortest_paths (returns paths) and distances (returns total weight) but that would mean calculating things twice. NB, I have weights in my graph. Is there a function to quickly calculate the total weight of a path?

> print(g)
IGRAPH 6c62431 DNW- 14 28 -- 
+ attr: name (v/c), weight (e/n)
+ edges from 6c62431 (vertex names):
 [1] src  ->i1-j1 src  ->i1-j2 src  ->i1-j3 src  ->i1-j4 i1-j1->i2-j2
 [6] i1-j1->i2-j3 i1-j1->i2-j4 i1-j1->i2-j5 i1-j2->i2-j3 i1-j2->i2-j4
[11] i1-j2->i2-j5 i1-j3->i2-j4 i1-j3->i2-j5 i1-j4->i2-j5 i2-j2->i3-j3
[16] i2-j2->i3-j4 i2-j2->i3-j5 i2-j2->i3-j6 i2-j3->i3-j4 i2-j3->i3-j5
[21] i2-j3->i3-j6 i2-j4->i3-j5 i2-j4->i3-j6 i2-j5->i3-j6 i3-j3->snk  
[26] i3-j4->snk   i3-j5->snk   i3-j6->snk  
> shortest_paths(g,from="src",to=c("snk"),output="both")
$vpath
$vpath[[1]]
+ 5/14 vertices, named, from 6c62431:
[1] src   i1-j1 i2-j4 i3-j5 snk  


$epath
$epath[[1]]
+ 4/28 edges from 6c62431 (vertex names):
[1] src  ->i1-j1 i1-j1->i2-j4 i2-j4->i3-j5 i3-j5->snk  


$predecessors
NULL

$inbound_edges
NULL

> distances(g,v=c("src"),to=c("snk"))
    snk
src  16 
question from:https://stackoverflow.com/questions/65937876/shortest-path-path-length-in-igraph

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

This seems to work:

> sp <- shortest_paths(g,from="src",to="snk",output="both")
> sp["vpath"][[1]][[1]]
+ 12/112 vertices, named, from 1e5c3a5:
 [1] src     i1-j2   i2-j5   i3-j7   i4-j8   i5-j11  i6-j12  i7-j13  i8-j14 
[10] i9-j15  i10-j17 snk    
> sum(E(g)$weight[sp["epath"][[1]][[1]]])
[1] 8860.797

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...