インターネットのルーティングなどのときに使う最短経路問題を解く方法（ダイクストラ法）のPythonでの実装
tracerouteをした時に表示される、インターネットのホストを経由するなどの最短経路を求める問題。
大学の時にクラスメイトに「高校の時分、このプログラムを作ったぞ」と言われ、長年簡単に解けると思っていたけれど、随分手子摺ったので、演習問題としてここに掲載しておきます。「共通一次試験で900点取ったぞ」と言われ、悔しいがそいつは優秀だった。
Qiitaの@gomagoma000さんの、コードを少しアレンジしたものです。概念的に理解したものの、オリジナルが素晴らしくよくできていて、改良の余地がありませんでした。動作する形にして掲載しておきます。何でこんなに良くできているのに、オリジナルの方にいいねが少ないのだろうか。真価の解る人があまりいないのだろうか。
例えば、ポイントnからポイントmへのコストと、ポイントmからポイントnへのコストが非対称な場合も記述できます。
shortest_path_problem.py
#!/usr/bin/python3
import heapq
net = {
'p0':{'p1':2,'p2':4,'p5':8},
'p1':{'p0':2,'p2':3,'p4':5},
'p2':{'p0':4,'p3':7},
'p3':{'p2':7,'p4':6},
'p4':{'p1':5,'p3':6,'p5':11},
'p5':{'p0':8,'p4':11}
}
def dijkstra(net, start, end):
que = [(0, start, [])]
seen = set()
_min = {start: 0}
while que:
(cost, node, path) = heapq.heappop(que)
if node not in seen:
seen.add(node)
path = path + [node]
if node == end:
return cost, path
for next_node, next_cost in net[node].items():
prev_cost = _min.get(next_node, False)
next_cost += cost
if prev_cost is False or next_cost < prev_cost:
heapq.heappush(que, (next_cost, next_node, path))
_min[next_node] = next_cost
return float("inf"), []
def main():
points = ['p'+str(i) for i in range(len(net))]
for start in points:
for end in points:
if start != end:
cost, path = dijkstra(net, start, end)
print(f"{start} to {end} : cost={cost}, route={path}")
if __name__=='__main__':
main()
exit(0)