小书匠Graph图论

重头戏部分来了,写到这里我感觉得仔细认真点了,可能在NetworkX中,实现某些算法就一句话的事,但是这个算法是做什么的,用在什么地方,原理是怎么样的,不清除,所以,我决定先把图论中常用算法弄个明白在写这部分.

图论常用算法看我的博客:

下面我将使用NetworkX实现上面的算法,建议不清楚的部分打开两篇博客对照理解.

我将图论的经典问题及常用算法的总结写在下面两篇博客中:

图论---问题篇

 图论---算法篇

11.Graph相关算法
- 11.1最短路径

注意:如果代码出现找不库,请返回第一个教程,把库文件导入.

11.Graph相关算法

11.1最短路径

11.1.1无向图和有向图

#定义并画出该图
G = nx.path_graph(5)
nx.add_path(G,[0,5,2])
nx.add_path(G,[0,6,4])
nx.draw(G,with_labels=True)
plt.title('无向图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
#计算最短路径
print('0节点到4节点最短路径: ',nx.shortest_path(G, source=0, target=4))
p1 = nx.shortest_path(G, source=0)
print('0节点到所有节点最短路径: ',p1)
#计算图中所有的最短路径
print('计算图中节点0到节点2的所有最短路径: ',[p for p in nx.all_shortest_paths(G, source=0, target=2)])
#计算最短路径长度
p2=nx.shortest_path_length(G, source=0, target=2) #最短路径长度
p3=nx.average_shortest_path_length(G) #计算平均最短路径长度
print('节点0到节点2的最短路径长度:',p2,' 平均最短路径长度: ',p3)
#检测是否有路径
print('检测节点0到节点2是否有路径',nx.has_path(G,0,2))

无向图和有向图最短路径示例

输出:

0节点到4节点最短路径: [0, 6, 4]

0节点到所有节点最短路径: {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 6, 4], 5: [0, 5], 6: [0, 6]}

计算图中节点0到节点2的所有最短路径: [[0, 1, 2], [0, 5, 2]]

节点0到节点2的最短路径长度: 2 平均最短路径长度: 1.8095238095238095

检测节点0到节点2是否有路径 True

11.1.2无权图

G = nx.path_graph(3)
nx.draw(G,with_labels=True)
plt.title('无权图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
path1 = nx.single_source_shortest_path(G, 0) #计算当前源与所有可达节点的最短路径
length1 = nx.single_source_shortest_path_length(G, 0) #计算当前源与所有可达节点的最短路径的长度
path2 = dict(nx.all_pairs_shortest_path(G)) #计算graph两两节点之间的最短路径
length2 = dict(nx.all_pairs_shortest_path_length(G)) #计算graph两两节点之间的最短路径的长度
prede1=nx.predecessor(G, 0) #返回G中从源到所有节点最短路径的前驱
print('当前源与所有可达节点的最短路径: ',path1,'\n当前源与所有可达节点的最短路径的长度: ',length1)
print('\ngraph两两节点之间的最短路径: ',path2,'\ngraph两两节点之间的最短路径的长度: ',length2)
print('\nG中从源到所有节点最短路径的前驱: ',prede1)

无权图

输出:

当前源与所有可达节点的最短路径: {0: [0], 1: [0, 1], 2: [0, 1, 2]}

当前源与所有可达节点的最短路径的长度: {0: 0, 1: 1, 2: 2}

graph两两节点之间的最短路径: {0: {0: [0], 1: [0, 1], 2: [0, 1, 2]}, 1: {0: [1, 0], 1: [1], 2: [1, 2]}, 2: {0: [2, 1, 0], 1: [2, 1], 2: [2]}}

graph两两节点之间的最短路径的长度: {0: {0: 0, 1: 1, 2: 2}, 1: {0: 1, 1: 0, 2: 1}, 2: {0: 2, 1: 1, 2: 0}}

G中从源到所有节点最短路径的前驱: {0: [], 1: [0], 2: [1]}

11.1.3有权图(迪杰斯特拉)

G = nx.path_graph(5, create_using = nx.DiGraph())
nx.draw(G,with_labels=True)
plt.title('有向图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
#计算加权图最短路径长度和前驱
pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)
print('\n加权图最短路径长度和前驱: ',pred, dist)
#返回G中从源到目标的最短加权路径,要求边权重必须为数值
print('\nG中从源0到目标4的最短加权路径: ',nx.dijkstra_path(G,0,4))
print('\nG中从源0到目标4的最短加权路径的长度: ',nx.dijkstra_path_length(G,0,4)) #最短路径长度
#单源节点最短加权路径和长度。
length1, path1 = nx.single_source_dijkstra(G, 0)
print('\n单源节点最短加权路径和长度: ',length1, path1)
#下面两条和是前面的分解
# path2=nx.single_source_dijkstra_path(G,0)
# length2 = nx.single_source_dijkstra_path_length(G, 0)
#print(length1,'$', path1,'$',length2,'$',path2)
#多源节点最短加权路径和长度。
path1 = nx.multi_source_dijkstra_path(G, {0, 4})
length1 = nx.multi_source_dijkstra_path_length(G, {0, 4})
print('\n多源节点最短加权路径和长度:', path1,length1)
#两两节点之间最短加权路径和长度。
path1 = dict(nx.all_pairs_dijkstra_path(G))
length1 = dict(nx.all_pairs_dijkstra_path_length(G))
print('\n两两节点之间最短加权路径和长度: ',path1,length1)
#双向搜索的迪杰斯特拉
length, path = nx.bidirectional_dijkstra(G, 0, 4)
print('\n双向搜索的迪杰斯特拉:',length, path)

迪杰斯特拉算法使用

输出:

加权图最短路径长度和前驱: {0: [], 1: [0], 2: [1], 3: [2], 4: [3]} {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}

G中从源0到目标4的最短加权路径: [0, 1, 2, 3, 4]

G中从源0到目标4的最短加权路径的长度: 4

单源节点最短加权路径和长度: {0: 0, 1: 1, 2: 2, 3: 3, 4: 4} {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}

多源节点最短加权路径和长度: {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [4]} {0: 0, 1: 1, 2: 2, 3: 3, 4: 0}

两两节点之间最短加权路径和长度: {0: {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}, 1: {1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]}, 2: {2: [2], 3: [2, 3], 4: [2, 3, 4]}, 3: {3: [3], 4: [3, 4]}, 4: {4: [4]}} {0: {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}, 1: {1: 0, 2:1, 3: 2, 4: 3}, 2: {2: 0, 3: 1, 4: 2}, 3: {3: 0, 4: 1}, 4: {4: 0}}

双向搜索的迪杰斯特拉: 4 [0, 1, 2, 3, 4]

11.1.4贝尔曼-福特(Bellman-Ford)算法

G = nx.path_graph(5, create_using = nx.DiGraph())
nx.draw(G,with_labels=True)
plt.title('有权图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
print('G中从源到目标的最短加权路径: ',nx.bellman_ford_path(G, 0, 4))
print('\nG中从源到目标的最短加权路径的长度:',nx.bellman_ford_path_length(G,0,4))
path1=nx.single_source_bellman_ford_path(G,0)
length1 = dict(nx.single_source_bellman_ford_path_length(G, 0))
print('\n单源节点最短加权路径和长度: ',path1,'\n单源节点最短加权路径和长度: ',length1)
path2 = dict(nx.all_pairs_bellman_ford_path(G))
length2 = dict(nx.all_pairs_bellman_ford_path_length(G))
print('\n两两节点之间最短加权路径和长度: ',path2,length2)
length, path = nx.single_source_bellman_ford(G, 0)
pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0)
print('\n加权图最短路径长度和前驱: ',pred,dist)

贝尔曼-福特(Bellman-Ford)算法使用示例

输出:

G中从源到目标的最短加权路径: [0, 1, 2, 3, 4]

G中从源到目标的最短加权路径的长度: 4

单源节点最短加权路径和长度: {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}

单源节点最短加权路径和长度: {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}

两两节点之间最短加权路径和长度: {0: {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}, 1: {1: [1], 2: [1, 2], 3: [1, 2, 3], 4:

[1, 2, 3, 4]}, 2: {2: [2], 3: [2, 3], 4: [2, 3, 4]}, 3: {3: [3], 4:

[3, 4]}, 4: {4: [4]}} {0: {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}, 1: {1: 0, 2:

1, 3: 2, 4: 3}, 2: {2: 0, 3: 1, 4: 2}, 3: {3: 0, 4: 1}, 4: {4: 0}}

加权图最短路径长度和前驱: {0: [None], 1: [0], 2: [1], 3: [2], 4: [3]} {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}

11.1.5检测负权重边

#定义并画出该图
G = nx.cycle_graph(5, create_using = nx.DiGraph())
#添加负权重边前后
print(nx.negative_edge_cycle(G))
G[1][2]['weight'] = -7
print(nx.negative_edge_cycle(G))

输出:

False

True

11.1.6使用约翰逊(Johnson)的算法

#生成graph
G = nx.DiGraph()
G.add_weighted_edges_from([('0', '3', 3), ('0', '1', -5),('0', '2', 2), ('1', '2', 4), ('2', '3', 1)])
#边和节点信息
edge_labels = nx.get_edge_attributes(G,'weight')
labels={'0':'0','1':'1','2':'2','3':'3'}
#生成节点位置
pos=nx.spring_layout(G)
#把节点画出来
nx.draw_networkx_nodes(G,pos,node_color='g',node_size=500,alpha=0.8)
#把边画出来
nx.draw_networkx_edges(G,pos,width=1.0,alpha=0.5,edge_color='b')
#把节点的标签画出来
nx.draw_networkx_labels(G,pos,labels,font_size=16)
#把边权重画出来
nx.draw_networkx_edge_labels(G, pos, edge_labels)
#显示graph
plt.title('有权图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
#使用johnson算法计算最短路径
paths = nx.johnson(G, weight='weight')
print(paths)

约翰逊(Johnson)的算法使用示例

输出:

{'2': {'2': ['2'], '3': ['2', '3']}, '3': {'3': ['3']}, '0': {'2': ['0', '1', '2'], '3': ['0', '1', '2', '3'], '0': ['0'], '1': ['0','1']}, '1': {'2': ['1', '2'], '3': ['1', '2', '3'], '1': ['1']}}

11.1.7弗洛伊德算法(Floyd-Warshall)

#使用Floyd算法找到所有对最短路径长度。
G = nx.DiGraph()
G.add_weighted_edges_from([('0', '3', 3), ('0', '1', -5),('0', '2', 2), ('1', '2', 4), ('2', '3', 1)])
#边和节点信息
edge_labels = nx.get_edge_attributes(G,'weight')
labels={'0':'0','1':'1','2':'2','3':'3'}
#生成节点位置
pos=nx.spring_layout(G)
#把节点画出来
nx.draw_networkx_nodes(G,pos,node_color='g',node_size=500,alpha=0.8)
#把边画出来
nx.draw_networkx_edges(G,pos,width=1.0,alpha=0.5,edge_color='b')
#把节点的标签画出来
nx.draw_networkx_labels(G,pos,labels,font_size=16)
#把边权重画出来
nx.draw_networkx_edge_labels(G, pos, edge_labels)
#显示graph
plt.title('有权图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
#计算最短路径长度
lenght=nx.floyd_warshall(G, weight='weight')
#计算最短路径上的前驱与路径长度
predecessor,distance1=nx.floyd_warshall_predecessor_and_distance(G, weight='weight')
#计算两两节点之间的最短距离,并以numpy矩阵形式返回
distance2=nx.floyd_warshall_numpy(G, weight='weight')
print(list(lenght))
print(predecessor)
print(list(distance1))
print(distance2)

弗洛伊德算法(Floyd-Warshall)使用示例

输出:

['2', '3', '0', '1']

{'2': {'3': '2'}, '0': {'2': '1', '3': '2', '1': '0'}, '1': {'2': '1', '3': '2'}}

['2', '3', '0', '1']

[[ 0. 1. inf inf]

[inf 0. inf inf]

[-1. 0. 0. -5.]

[ 4. 5. inf 0.]]

注:输出中的矩阵不是按照节点0,1,2,3排序,而是2,1,3,0,即如图:

两点之间的最短距离

11.1.8A*算法

G = nx.path_graph(5)
#显示graph
nx.draw(G,with_labels=True)
plt.title('有x向图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
#直接输出路径和长度
print(nx.astar_path(G, 0, 4))
print(nx.astar_path_length(G, 0, 4))

A*算法

输出:

[0, 1, 2, 3, 4]

4

巴特西

NetworkX系列教程(10)-算法之一:最短路径问题

11.Graph相关算法

11.1最短路径

11.1.1无向图和有向图

11.1.2无权图

11.1.3有权图(迪杰斯特拉)

11.1.4贝尔曼-福特(Bellman-Ford)算法

11.1.5检测负权重边

11.1.6使用约翰逊(Johnson)的算法

11.1.7弗洛伊德算法(Floyd-Warshall)

11.1.8A*算法

最新文章

热门文章