Dijkstra最短路径算法

class BuildGraph:
    def __init__(self):
        self.G = dict()

    def __call__(self, *args, **kwargs):
        graph_info = args[0]
        for item in graph_info:
            if item[0] not in self.G:
                self.G[item[0]] = dict()
            if item[1] not in self.G:
                self.G[item[1]] = dict()
            self.G[item[0]][item[1]] = self.G[item[1]][item[0]] = item[2]
        return self

    def get(self):
        return self.G


class Dijkstra:
    Nan = 1 << 32

    def __init__(self, G):
        self.G = G

    def __call__(self, *args, **kwargs):
        s = args[0]  # start vertex
        e = args[1]  # end vertex

        S = set()
        V = set()
        L = dict()
        DL = list()

        for key in self.G:
            L[key] = Dijkstra.Nan
            V.add(key)
        L[s] = 0
        u = None
        while u != e and V:
            # find minimum value
            u = None
            for v in V:
                if not u or L[u] > L[v]:
                    u = v
            # update information
            S.add(u)
            V.remove(u)
            DL.append(u)
            for v, d in self.G[u].items():
                if v not in S and L[u] + self.G[u][v] < L[v]:
                    L[v] = L[u] + self.G[u][v]

        return DL, L[e]


if __name__ == '__main__':
    graph_info = [('a', 'b', 4), ('a', 'c', 2), ('b', 'c', 1), ('b', 'd', 5), 
                 ('c', 'd', 8), ('c', 'e', 10), ('d', 'e', 2), ('d', 'z', 6), ('e', 'z', 3)]
    print(Dijkstra(BuildGraph()(graph_info).get())('a', 'z'))

算法原理.png 算法演示图.png

该算法如果使用描述性的语言即便说清楚了，看的人还是会一头雾水，主要的原因是这个算法设计的逻辑点比较多，这个也说明了这个算法的技巧性很强，所以，我根据自己的经验，就是多多体会，这个体会是需要一定的时间的，不是说你看懂一遍或者自己能写一遍就OK了，这个是需要慢慢成长的过程！！！

简图.png

从上面的摘的段落也可以看出，程序描述和证明都不是一件十分容易的事情，这个也说明了，如果我们想要自己更进一步其实很简单，但是也很难，简单的是只要肯努力学习这些基本的概念你就会有所收获，难的是不是简单的弄清概念就行的，更多的是体会，这种东西很难说的明白的。