Hi, I am a newbie and have been struggling over the past couple of days with dijkstra_shortest_paths. I want to use WeightMap as an external property. I create the Graph as follows typedef boost::adjacency_list<boost::vecS,boost::vecS, boost::directedS,boost::no_property, boost::property<boost::edge_index_t, std::size_t> > Graph; I added edges using add_edge(fromVertex, toVertex, edge_index, Graph); My edge_index can have any long value and they are not necessarily in sequence. Also, I want to create the weight map on the fly and want to use a std::map. I have tried all sorts of things but to no avail. Any help will be appreciated. Thanks, Rohit.