怎样用STL中的list建立一个有向加权图

Question

请问各位高手，怎样用STL中的list建立一个有向加权图，并用Dijkstra算法查找两点间的距离？急

Answer 1

用list建立一个有向加权图不难，只要用list< list<int> > 就可以存储所有的权值了。
但是要用这个有向加权图采用Dijkstra算法计算两个点之间的距离就难了。
因为Dijkstra算法的每一步比较中需要读取任意两个节点之间的距离，这用list虽然也可以实现，但是会非常缓慢。N个数据，如果以数组存的话，读取其中的一个元素平均需要1步；
以vector存的话，也需要1步；
而以list存的话，平均需要N /2步。这个网页中有Dijkstra算法的演示：
http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm这个网页中有Dijkstra算法的源码：
http://www.codeproject.com/cpp/GcDijkstra.asp