List Info

Thread: how to use dijkstra's shortest path algorithm
how to use dijkstra's shortest path algorithm
country flaguser name
United Kingdom		 2007-02-25 12:59:24 

  


  

    
Hi everyone,

I am completely new to Boost, and have been playing with it through the python bindings, but I'm getting a bit confused. 

What I'm trying to do is use dijkstra's shortest path algorithm (with predecessor) on a graph I'm reading in from a graphviz file. My code is as below:

import boost.graph as bgl

#Create a new graph from the graphviz file
graph = bgl.Graph.read_graphviz('code/mst.dot')
#try to get shortest path
min_paths = bgl.dijkstra_shortest_paths(graph,graph.vertices.next(),predecessorMap,distanceMap)

which is the way variables should be entered according to the documentation.

dijkstra_shortest_paths(graph, root_vertex, ;predecessor_map = None, 

      ;           ;       distance_map = None, weight_map = None, 

   ;           ;          visitor = None)

I'm not completely sure what I'm doing wrong. Basically, I would like to get the predecessors and then print them out to screen.

And finally, how do you actually access a single vertex. Say I want vertex one of my graph, or vertex two or whatever. Do I have to iterate over until I get there or is there an easier way?

Thanks (sorry is this has already been posted. I searched but couldn't find a previous posting)

Neeraj






		
 
All New Yahoo! Mail – Tired of unwanted email come-ons? Let our SpamGuard protect you.		
  

  
  
   
     
    

  

    Re:  how to use dijkstra's shortest path
algorithm
  


  

     country flaguser name
United States		
     2007-02-26 07:55:23
  


  

    
On Feb 25, 2007, at 1:59 PM, Neeraj Shah wrote:

> Hi everyone,
>
> I am completely new to Boost, and have been playing
with it through  
> the python bindings, but I'm getting a bit confused.
>
> What I'm trying to do is use dijkstra's shortest path
algorithm  
> (with predecessor) on a graph I'm reading in from a
graphviz file.  
> My code is as below:
>
> import boost.graph as bgl
>
> #Create a new graph from the graphviz file
> graph = bgl.Graph.read_graphviz('code/mst.dot')
> #try to get shortest path
> min_paths =
bgl.dijkstra_shortest_paths(graph,graph.vertices.next 
> (),predecessorMap,distanceMap)

You'll need to initialize predecessorMap and distanceMap to 

something, e.g.,

	distanceMap = graph.add_vertex_property('distance')
	predecessorMap = graph.add_vertex_property('predecessor')

(Assuming you're using the Subversion version of BGL-Python;
it's  
slightly different for 0.9)

	Cheers,
	Doug

------------------------------------------------------------
-------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the
chance to share your
opinions on IT & business topics through brief
surveys-and earn cash
http://www.techsay.com/default.
php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Boost-langbinding mailing list
Boost-langbindinglists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/boost
-langbinding



  


  

    
  

  
  
   
     
    






 [1-2]











   
 





about | contact  Other archives ( Real Estate discussion Medical topics )