[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Generating Dijkstra Shortest Path
From: |
Ronquillo, Edgar Nahum |
Subject: |
Re: [igraph] Generating Dijkstra Shortest Path |
Date: |
Mon, 22 Jun 2015 13:02:54 +0000 |
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