以下の例題では、ノード間に高々1本の有向道路があり、移動コストが道路に与えられている。ノードを a, b とし、有向道路のコストが a から b は c で、b から a は d としている。つまり、隣接リストとしては、to[a] = (b, c)、to[b] = (a, d) になる。

全体のノード数は V で与えられる。スタートノードは start、ゴールとなるノードは goal。

INF = 0x7fffffff
import heapq
def dijkstra(V, to, start, goal):
	dist = [INF]*V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] < t: continue
		for e, cost in to[s]:
			nt = t + cost
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
	return dist[goal]

Python3では、プライオリティキュー(minキュー)の使い方は以下のとおり。

#heapq
import heapq                        # heapq のインポート
Q = []                                  # キューの作成
heapq.heappush(Q, (cost, node))     # 要素の追加
cost, node = heapq.heappop(Q)       # 要素の取り出す

Qでの要素はタプルとして定義する。タプルの最初はキーとなるもの、2番め以降は自由に追加して良さそう。

上記のダイクストラ関数を利用した例は以下に示す。AOJ-117という問題。

n = int(input())+1
to = [[] for i in range(n)]
for i in range(int(input())):
	a, b, c, d = list(map(int, input().split(',')))
	to[a].append((b, c))
	to[b].append((a, d))
s, g, V, P = list(map(int, input().split(',')))
if s == g: print(V-P)
else: print(V-P - dijkstra(n, to, s, g) - dijkstra(n, to, g, s))

ノード番号は1-indexとして入力時に与えられるので、全体のノード数を最初の行で1つ増やしておいた。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Post Navigation