Graph algorithms: Prim,Kruskal, Dijkstra, Floyd

2015-05-31 by muzi

最近有了一点点空闲时间,想想以后的项目肯定是需要用到图中的路径算法,于是花了一些时间把4大经典算法实现了一遍。算法实现水平不高,时间复杂度都太高了一点。但是逻辑相对比较清晰,测试结果正确。如果读者发现算法中的问题,敬请指出,万分感谢。

Prim

Prim算法是最小生成树算法的一种,其算法逻辑为:

从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。 输入:一个加权连通图,其中顶点集合为V,边集合为E;

初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {}; 重复下列操作,直到Vnew = V:

1:在集合E中选取权值最小的边(u,v),其中u为集合Vnew中的元素,而v则是V中没有加入Vnew的顶点(如果存在有多条 满足前述条件即具有相同权值的边,则可任意选取其中之一); 2:将v加入集合Vnew中,将(u, v)加入集合Enew中;

输出:使用集合Vnew和Enew来描述所得到的最小生成树。

算法实现采用数据结构为邻接矩阵,实现如下:

    def prim(graph, root):
        assert type(graph)==dict

        nodes = graph.keys()
        nodes.remove(root)

        visited = [root]
        path = []
        next = None

        while nodes:
            distance = float('inf') 
            for s in visited:
                for d in graph[s]:
                    if d in visited or s == d:
                        continue
                    if graph[s][d] < distance:
                        distance = graph[s][d]
                        pre = s
                        next = d
            path.append((pre, next))
            visited.append(next)
            nodes.remove(next)

        return path


    if __name__ == '__main__':
        graph_dict = {  "s1":{"s1": 0, "s2": 2, "s10": 3, "s12": 4, "s5":3},
                        "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
                        "s10":{"s1": 2, "s2": 6, "s10": 0, "s12":3, "s5":4},
                        "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":2},
                        "s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
        }

        path = prim(graph_dict, 's12')
        print path

Kruskal

Kruskal是另一种最小生成树的算法,相比Prim算法,Kruskal算法采用避圈法进行最小树生长。算法逻辑为:

1:新建图G,G中拥有原图中相同的节点,但没有边 2:将原图中所有的边按权值从小到大排序 3:从权值最小的边开始,如果这条边连接的两个节点于图G中不在同一个连通分量中,则添加这条边到图G中 4:重复3,直至图G中所有的节点都在同一个连通分量中

实现代码如下:

    def kruskal(graph):
        assert type(graph)==dict

        nodes = graph.keys()   
        visited = set()
        path = []
        next = None

        while len(visited) < len(nodes):
            distance = float('inf') 
            for s in nodes:
                for d in nodes:
                    if s in visited and d in visited or s == d:
                        continue
                    if graph[s][d] < distance:
                        distance = graph[s][d]
                        pre = s
                        next = d

            path.append((pre, next))
            visited.add(pre)
            visited.add(next)

        return path


    if __name__ == '__main__':
        graph_dict = {  "s1":{"s1": 0, "s2": 6, "s10": 3, "s12": 4, "s5":3},
                        "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 3, "s5":4},
                        "s10":{"s1": 2, "s2": 6, "s10": 0, "s12":3, "s5":4},
                        "s12":{"s1": 1, "s2": 5, "s10": 2, "s12":0,"s5":2},
                        "s5":{"s1": 3, "s2": 5, "s10": 7, "s12":4,"s5":0},
        }

        path = kruskal(graph_dict)
        print path

Dijkstra

Diikstra算法是用于计算某源点到其他节点的最短路径的算法。其算法逻辑为:

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时,原点 s 的路径长度值被赋为 0 (d[s] = 0),若存在能直接到达的边(s,m),则把d[m]设为w(s,m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于 V 中所有顶点 v 除 s 和上述 m 外 d[v] = ∞)。当算法结束时,d[v] 中存储的便是从 s 到 v 的最短路径,或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展:如果存在一条从 u 到 v 的边,那么从 s 到 v 的最短路径可以通过将边(u, v)添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小,我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 d[u] 达到它最终的值的时候每条边(u, v)都只被拓展一次。 算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点,而集合 Q 则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中,算法对每条外接边 (u, v) 进行拓展。

算法实现如下:

    def dijkstra(graph,src):
        length = len(graph)
        type_ = type(graph)
        if type_ == list:
            nodes = [i for i in xrange(length)]
        elif type_ == dict:
            nodes = graph.keys()

        visited = [src]
        path = {src:{src:[]}}
        nodes.remove(src)
        distance_graph = {src:0}
        pre = next = src

        while nodes:
            distance = float('inf')
            for v in visited:
                 for d in nodes:
                    new_dist = graph[src][v] + graph[v][d]
                    if new_dist <= distance:
                        distance = new_dist
                        next = d
                        pre = v
                        graph[src][d] = new_dist


            path[src][next] = [i for i in path[src][pre]]
            path[src][next].append(next)

            distance_graph[next] = distance

            visited.append(next)
            nodes.remove(next)

        return distance_graph, path


    if __name__ == '__main__':
        graph_list = [   [0, 2, 1, 4, 5, 1],
                [1, 0, 4, 2, 3, 4],
                [2, 1, 0, 1, 2, 4],
                [3, 5, 2, 0, 3, 3],
                [2, 4, 3, 4, 0, 1],
                [3, 4, 7, 3, 1, 0]]

        graph_dict = {  "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3},
                        "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
                        "s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4},
                        "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1},
                        "s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
        }

        distance, path = dijkstra(graph_list, 2)
        #print distance, '\n', path
        distance, path = dijkstra(graph_dict, 's1')

Floyd

Floyd是一种计算图中所有点到其他点最短路径的算法。与Dijkstra算法相比,可以允许边值为负数。算法逻辑如下:

设D_{i,j,k}为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

若最短路径经过点k,则D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}; 若最短路径不经过点k,则D_{i,j,k}=D_{i,j,k-1}。

因此,D_{i,j,k}=\mbox{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})。

代码实现如下:

    def floyd(graph):
        length = len(graph)
        path = {}

        for i in xrange(length):
            path.setdefault(i, {})
            for j in xrange(length):
                if i == j:
                    continue

                path[i].setdefault(j, [i,j])
                new_node = None

                for k in xrange(length):
                    if k == j:
                        continue

                    new_len = graph[i][k] + graph[k][j]
                    if graph[i][j] > new_len:
                        graph[i][j] = new_len
                        new_node = k
                if new_node:
                    path[i][j].insert(-1, new_node)

        return graph, path

    def floyd_dict(graph):
        length = len(graph)
        path = {}

        for src in graph:
            path.setdefault(src, {})
            for dst in graph[src]:
                if src == dst:
                    continue
                path[src].setdefault(dst, [src,dst])
                new_node = None

                for mid in graph:
                    if mid == dst:
                        continue

                    new_len = graph[src][mid] + graph[mid][dst]
                    if graph[src][dst] > new_len:
                        graph[src][dst] = new_len
                        new_node = mid
                if new_node:
                    path[src][dst].insert(-1, new_node)

        return graph, path


    if __name__ == '__main__':
        ini = float('inf')
        graph_list = [   [0, 2, 1, 4, 5, 1],
                [1, 0, 4, 2, 3, 4],
                [2, 1, 0, 1, 2, 4],
                [3, 5, 2, 0, 3, 3],
                [2, 4, 3, 4, 0, 1],
                [3, 4, 7, 3, 1, 0]]

        graph_dict = {  "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4},
                        "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2},
                        "s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1},
                        "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0},
        }

        #new_graph, path= floyd_dict(graph_dict)    
        new_graph, path = floyd(graph_list)
        print new_graph, '\n\n\n', path

总结

这几个算法都是图论中的经典算法,会在网络应用中经常用到。然而我的实现只是最简单逻辑的实现,并没有考虑太多性能上的问题。如果需要追求性能,我想还是需要谷歌一下,或者到Github上随意挑选。获取代码可点击链接:graph algorithms


Comments