単一始点最短距離問題をPythonで解答

負の閉路が存在しない場合、更新はいずれ止まるため、この更新方法で対応できるらしい。

## ベルマンフォード法

class BellmanFord(object):
    def __init__(self, v):
        self.e = 0
        self.d = [float("inf") for i in range(v)]
        self.edge = []

    def append(self, _from, _to, _cost):
        self.edge.append({
            'from': _from, 'to': _to, 'cost': _cost
        })
        self.e = len(self.edge)

    def shortest_path(self, s):
        self.d[s] = 0
        while 1:
            update = True
            for i in range(self.e):
                e = self.edge[i]
                if self.d[e['from']] != float("inf") and self.d[e['to']] > self.d[e['from']] + e['cost']:
                    self.d[e['to']] = self.d[e['from']] + e['cost']
                    update = True
            if update:
                break


## ダイクストラ法

class Dijkstra(object):
    def __init__(self, v):
        self.v = v
        self.e = 0
        self.d = [float("inf") for i in range(v)]
        self.used = [0 for  i in range(v)]
        self.cost = [[float("inf") for i in range(v)] for i in range(v)]

    def append(self, _from, _to, _cost):
        self.cost[_from][_to] = _cost
        self.e += 1

    def shortest_path(self, s):
        self.d[s] = 0
        while 1:
            v = -1

            for u in range(self.v):
                if not self.used[u] and (v == -1 or (self.d[u] < self.d[v])):
                    v = u
            if (v == -1):
                break

            self.used[v] = 1

            for u in range(self.v):
                self.d[u] = min(self.d[u], self.d[v] + self.cost[v][u])

b = BellmanFord(7)
b.append(0, 1, 2)
b.append(1, 0, 2)
b.append(0, 2, 5)
b.append(2, 0, 5)
b.append(1, 2, 4)
b.append(2, 1, 4)
b.append(1, 3, 6)
b.append(3, 1, 6)
b.append(2, 3, 2)
b.append(3, 2, 2)
b.append(1, 4, 10)
b.append(4, 1, 10)
b.append(3, 5, 1)
b.append(5, 3, 1)
b.append(4, 5, 3)
b.append(5, 4, 3)
b.append(4, 6, 5)
b.append(6, 4, 5)
b.append(5, 6, 9)
b.append(6, 5, 9)

b.shortest_path(0)

In [40]: b.d
Out[40]: [0, 2, 5, 7, 11, 8, 16]

In [41]: b.d[6]
Out[41]: 16