calculating shortest path in graph using edge weight

[sergio]

Hi all,
I'm trying to calculate the shortest path in a graph using
path.shortest_path(G, source, dest).
The thing is that the function is considering all edges to have the
weight of 1.

How can I do in order to use the weights of the edges for the
calculation?

Here is an example:
G = NX.read_edgelist("file.txt", create_using= NX.XDiGraph())

In [39]: print G.edges()
[('A', 'B', '2'), ('C', 'B', '2'), ('C', 'D1', '2'), ('C', 'E', '2'),
('E', 'D1', '2') ..... ]

In [43]: NX.path.shortest_path(G, "A","D1")
Out[43]: ['A', 'B', 'C', 'D1']

In [42]: NX.path.shortest_path_length(G, "A","D1")
Out[42]: 3

#As I understand it, it is considering the length of 3 instead of 6

Thanks in advance

sergio

[Aric Hagberg]

On Wed, Sep 17, 2008 at 04:58:06PM -0700, sergio wrote:
>
> Hi all,
> I'm trying to calculate the shortest path in a graph using
> path.shortest_path(G, source, dest).
> The thing is that the function is considering all edges to have the
> weight of 1.
>
> How can I do in order to use the weights of the edges for the
> calculation?

Try "dijkstra_path_length(...) to get the shortest path length
of a weighted graph or digraph.

Aric

[sergio]

Hi Aric,

It looks like dijkstra works, but only if I use NX.XDiGraph() with
edge type int.
e.g. G = NX.read_edgelist("sample.txt", create_using= NX.XDiGraph(),
edgetype= int)
NX.path.dijkstra_path_length(G, "A", "I")

Thanks for the tip

sergio

[Sergio Carrilho]

Hi Aric,

I tried it and not work. Maybe I'm using a wrong format to represent weights?
The file has data in the format:
A B 2
B C 2
C D 3
etc

the result of the output was:

####
program:

In [49]: G = NX.read_edgelist("test.txt", create_using= NX.XDiGraph())

In [50]: NX.path.dijkstra_path_length(G, "A", "I")
---------------------------------------------------------------------------
Output:

Traceback (most recent call last):
  File "test.py", line 7, in <module>

    NX.path.dijkstra_path_length(G, "A", "I")

  File "/Library/Python/2.5/site-packages/networkx-0.37-py2.5.egg/networkx/path.py", line 257, in dijkstra_path_length
    (length,path)=single_source_dijkstra(G,source)
  File "/Library/Python/2.5/site-packages/networkx-0.37-py2.5.egg/networkx/path.py", line 438, in single_source_dijkstra
    vw_dist = dist[v] + G.get_edge(v,w)
TypeError: unsupported operand type(s) for +: 'int' and 'str'

####

Thanks

sergio

--
------------ooo00ooo------------
,,,       Sergio Carrilho
( ',')     (セルジオ　カリル)
<|"|>  
./"L    東京大学、江崎研究室
 ------------ooo00ooo------------