Dijkstra’s algorithm

dijkstra.py

# coding: utf-8

import collections

# http://habrahabr.ru/post/111361/
gr1 = {
    1: {2: 10, 3: 30, 4: 50, 5: 10},
    2: {},
    3: {5: 10},
    4: {3: 20, 2: 40},
    5: {1: 10, 3: 10, 4: 30},
}

# http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
gr2 = {
    1: {2: 7, 3: 9, 6: 14},
    2: {1: 7, 3: 10, 4: 15},
    3: {1: 9, 2: 10, 4: 11, 6: 2},
    4: {2: 15, 3: 11, 5: 6},
    5: {4: 6, 6: 9},
    6: {1: 14, 3: 2, 5: 9},
}


TaggedVertex = collections.namedtuple('TaggedVertex', ('vertex', 'value'))


class Dijkstra(object):

    def __init__(self, graph):
        self.graph = graph
        self.seen = set()
        self.tags = {v: float('inf') for v in self.graph.keys()}
        self.path_desc = None
        self.start_vertex = None

    def get_minimal_unseen_vertex(self):
        minimal = TaggedVertex(None, float('inf'))
        for v, value in self.tags.iteritems():
            if v in self.seen:
                continue
            if value < minimal.value:
                minimal = TaggedVertex(v, value)
        return minimal

    def run(self, start_vertex):
        self.start_vertex = start_vertex
        self.tags[start_vertex] = 0
        self.path_desc = {v: start_vertex for v in self.graph.keys()}
        while True:
            v, value = self.get_minimal_unseen_vertex()
            if v is None:
                # все вершины посещены
                break
            for adj_v, weight in self.graph.get(v, {}).iteritems():
                if adj_v in self.seen:
                    continue
                new_weight = value + weight
                if new_weight < self.tags[adj_v]:
                    self.tags[adj_v] = new_weight
                    self.path_desc[adj_v] = v
            self.seen.add(v)
        return self.tags

    def get_minimal_route(self, dest):
        route = collections.deque()
        vx = dest
        route.appendleft(vx)
        while vx != self.path_desc[vx]:
            vx = self.path_desc[vx]
            route.appendleft(vx)
        return route


def main():
    d = Dijkstra(gr2)
    result = d.run(1)
    print result
    print d.get_minimal_route(5)


if __name__ == '__main__':
    main()