我用Dijkstra算法,写了一个无环有向图的最短路径问题的解决方案。如果是无向图也很简单,把每个无向的edge拆开成两个有向的就可以解决了。

为了每次弹出正确的端点,我也实现了一个最小优先队列。

代码由4个类构成:

Edge定义两个端点之间路径,有三个属性:源,目的地和权重。

Graph定义了整个图形,包括路径和端点。在这个code里面,端点不能单独添加。当添加路径的时候,端点会自动添加。

MinPQ定义一个优先队列,它用来储存端点到起始点的最小距离。它有一个方法del_min,用来弹出队列中距离最小的那个端点。

ShortestPath是主要类,它使用Dijkstra算法,有两个方法:

path_to(vertex)方法返回包含从起点到顶点的最短路径的字符串。

dist_to(vertex)返回path_to(vertex)的总长度。

阅读原文 »

4 收藏


直接登录

推荐关注