初めに

よく最短経路問題を解くのにダイクストラ法が用いられていますが，pythonで実装されている方々のソースを拝見すると，皆さん隣接行列で書かれていることがほとんどです．少なくとも私調べで隣接リストで実装されている方が見当たらなかったので改変してのせます．
競技プログラミングを行うなら高速な隣接行列を用いるのだろうと思いますが，私の用途ではサイズが膨れ上がってしまうので・・・
あと，利点としてはIDがばらばらであったとしてもきちんと動作します．隣接行列ならばらばらだったとしてもIDの最大値x最大値分の配列を用意するか，IDと配列の間で紐づけを行う必要が・・・
元のなるプログラムはフツーって言うなぁ！さんからです．
変えたといってもリストを辞書に変えて，隣接リストをクラスを用いて作っただけですが・・・

Dijkstra_list.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
class NeighborList():
    def __init__(self):
        self.neighbor = {}
class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        dist = {} # 始点から各頂点までの最短距離を格納する
        prev = {} # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        prev[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in adj[src].neighbor.keys():
                cost = adj[src].neighbor[dest]#src→destのチェック

                if dest in dist.keys():
                    if dist[dest] > dist[src] + cost:#先のコスト(仮決定) > 今のコスト+移動するのにかかるコスト
                        dist[dest] = dist[src] + cost # distの更新
                        heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                        prev[dest] = src                      # 前の頂点IDを記録
                else:#訪れたことが無ければ
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点IDを記録

        if goal is not None:
            return self.get_path(start,goal, prev)
        else:
            return dist

    def get_path(self, start, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != start:
            path.append(prev[dest])
            dest = prev[dest]

        path.append(start)

        # 経路をreverseして出力
        return list(reversed(path))

if __name__ == '__main__':
    d = Dijkstra()
    n = {0:NeighborList(),1:NeighborList(),2:NeighborList(),3:NeighborList(),4:NeighborList()}
    n[0].neighbor[1] = 2
    n[0].neighbor[2] = 4

    n[1].neighbor[0] = 2
    n[1].neighbor[2] = 3
    n[1].neighbor[3] = 5

    n[2].neighbor[0] = 4
    n[2].neighbor[1] = 3
    n[2].neighbor[3] = 1
    n[2].neighbor[4] = 4

    n[3].neighbor[1] = 5
    n[3].neighbor[2] = 1
    n[3].neighbor[4] = 3

    n[4].neighbor[2] = 4
    n[4].neighbor[3] = 3

    result = d.dijkstra(n,0,4)
    print(result)

参考

フツーって言うなぁ！-Pythonでダイクストラアルゴリズムを実装した

ダイクストラ法を隣接リストを用いて実装する

初めに

参考