Re: [igraph] Generating Dijkstra Shortest Path

[Ronquillo, Edgar Nahum]

This worked! thanks

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Tamas Nepusz
Sent: Monday, June 22, 2015 3:11 AM
To: Help for igraph users
Subject: Re: [igraph] Generating Dijkstra Shortest Path

> G.shortest_paths_dijkstra(vertice1, vertice2) where vertice1 and 
> vertice2 represent the source and target, of course. I would like for 
> this to return a list of vertex names of the shortest path using the 
> weights/costs that I passed when I added the edges. Am I doing this correct?
Please read the documentation of shortest_paths_dijkstra():

http://igraph.org/python/doc/igraph.Graph-class.html#shortest_paths_dijkstra

You can see that the function has a "weights" argument with a default value of 
None. The documentation of the "weights" argument says:

"a list containing the edge weights. It can also be an attribute name (edge 
weights are retrieved from the given attribute) or None (all edges have equal 
weight)."

So, by default, shortest_paths_dijkstra() will not consider edge weights. You 
have to pass at least the name of the edge attribute containing weights 
("weight" in your case):

G.shortest_paths_dijkstra(vertex1, vertex2, weights="weight")

> I would like to print the shortest path of the vertex names I added 
> previously. I hope this is understandable.
Use get_shortest_paths() with the "weights" argument -- this will run 
Dijkstra's algorithm but return the indices of the vertices in the shortest 
paths instead:

http://igraph.org/python/doc/igraph.GraphBase-class.html#get_shortest_paths

paths = G.get_shortest_paths(vertex1, vertex2, weights="weight")

The result will be a list with one element: the path from vertex1 to vertex2.
Since the path contains vertex IDs by default, you need to map them to names:

path = paths[0]
path_with_names = G.vs[path]["name"]

T.

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