ダイクストラ法(Dijkstra's Algorithm)をpythonで実装する

やったこと

ダイクストラ法についての勉強を兼ねて、ダイクストラ法をpythonで実装してみた。

例題としては、「Dijkstra AtCoder」でググって最初に出てきた「AtCoder Beginner Contest 035 の D -トレジャーハント」を用いた。

ダイクストラ法とDFSやBFSの違い

ダイクストラ法とDFS、BFSの違いがよくわからなくなったので、調べた結果を簡単にまとめる。

（DFS、BFSについては下記で実装）
深さ優先探索(DFS)と幅優先探索(BFS)をpythonで実装する

• DFS(深さ優先探索)・BFS(幅優先探索)
  • 重みのないグラフについての探索を行うためのアルゴリズム
• ダイクストラ法
  • 重み付きグラフについての探索を行うためのアルゴリズム（キュー(正確には重み付きキュー)を用いるため、BFSの拡張版のイメージ）

Dijkstra's Algorithm

メモ

start→目的地に着くまでの最短経路をg_list,go
目的地→startに着くまでの最短経路をb_list,back で管理

# ABC035 D トレジャーハント

import heapq

def dijkstra(s, n, c_list):
    _list = [float("Inf")]*n
    _list[s] = 0
    hq = [[0,s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        _ci, _i = heapq.heappop(hq)
        if _list[_i] < _ci:
            continue
        for _cj,_j in c_list[_i]:
            if _list[_j] > (_list[_i] + _cj):
                _list[_j] = _list[_i] + _cj
                heapq.heappush(hq, [_list[_j],_j])
    return _list

n, m, t = map(int, input().split())
a_list = [int(x) for x in input().split()]
g_list = [[] for i in range(n)]
b_list = [[] for i in range(n)]

for i in range(m):
    _a, _b, _c = map(int, input().split())
    g_list[_a-1].append([_c,_b-1])
    b_list[_b-1].append([_c,_a-1])

go = dijkstra(0, n, g_list)
back = dijkstra(0, n, b_list)
ans = 0

for i in range(n):
    _tmp = t - (go[i] + back[i])
    if a_list[i]*_tmp > ans:
        ans = a_list[i]*_tmp

print(ans)