BYR Achieve · 镜像论坛

【以下文字转载自 StudyShare 讨论区】发信人: lc10210103 (summer~精彩呈现 http://www.muzixing.com), 信区: StudyShare 标题: 图论算法：Dijkstra, Floyd, Prim, Kruskal 发信站: 北邮人论坛 (Mon Jun 1 09:51:19 2015), 站内上周无聊花点时间完成了这几个算法，但是感觉实现上还是很low，算法还需要大大优化。不过基本的功能实现应该没有问题。由于排版蛋疼。可以查看：http://www.muzixing.com/pages/2015/05/31/graph-algorithms-primkruskal-dijkstra-floyd.html Prim: 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 Kruskal: 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 Dijkstra: 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 Floyd: 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 全部源码：https://github.com/muzixing/graph_algorithm

图论算法：Dijkstra, Floyd, Prim, Kruskal (转载)