Python实现迪杰斯特拉算法和贝尔曼福特算法求解最短路径
2019-08-05 本文已影响0人
XHHP
关于Python数据分析在数学建模中的更多相关应用：Python数据分析在数学建模中的应用汇总（持续更新中！）
（一）、题目
本题采用带权无向图作为例子。要求实现：
- 绘制带权无向图
- 获得从源结点到目的结点的最短路径
- 所有结点两两之间的最短路径
-
实现最短路径高亮
在这里插入图片描述
（二）、导库
最短路径问题主要使用的库是：
- networkx——内置常用的图与复杂网络分析算法
- matplotlib——使用matplotlib库进行绘图
import networkx as nx #内置常用的图与复杂网络分析算法
import matplotlib.pyplot as plt #使用matplotlib库进行绘图
（三）、绘制带权无向图
主要步骤：
- 初始化源节点、目的结点以及权
- 创建一个无向图，并将结点以及边添加到其中
- 生成结点位置（设置布局，取消轴线）
- 绘制结点、边、权
#初始化图
s = [0,0,1,1,7,7,2,8,2,6,2,3,3,5] #源结点
t = [1,7,7,2,8,6,8,6,5,5,3,5,4,4] #目的结点
w = [4,8,3,8,1,6,2,6,4,2,7,14,9,10] #权
#无向图的构建
G = nx.Graph() #创建一个无向图
for i in range(0,len(s)): #遍历每一条边
G.add_edge(s[i], t[i], weight = w[i]) #为图G添加边，并且附上权重weight
#生成节点位置
pos=nx.spring_layout(G) #设置布局
plt.xticks([]) #取消x轴的刻度
plt.yticks([]) #取消y轴的刻度
#把节点画出来
nx.draw_networkx_nodes(G,pos,node_color='r',node_size=500,alpha=0.8) #显示每一个结点
#把边画出来
nx.draw_networkx_edges(G,pos,width=3.0,alpha=0.5,edge_color='b') #显示每一条边
#把节点的标签画出来
nx.draw_networkx_labels(G,pos,font_size=16) #显示每一个结点上的数字
#把边权重画出来
edge_labels = nx.get_edge_attributes(G,'weight') #获取每一条边的权重
nx.draw_networkx_edge_labels(G, pos, edge_labels) #为图添加上权重
（四）、获得最短路径
主要内容：
- 使用迪杰斯特拉算法获得从源结点（source）到目的结点的最短路径长度
- 使用迪杰斯特拉算法获取从源结点（source）到目的结点的最短路径
- 使用贝尔曼-福特算法获得从源结点（source）到目的结点的最短路径长度
- 使用贝尔曼-福特算法获取从源结点（source）到目的结点的最短路径
- 使用迪杰斯特拉算法获得每两个节点之间的最短路径长度
- 使用迪杰斯特拉算法获得每两个节点之间的最短路径
def get(G):
#使用迪杰斯特拉算法获得从源结点（source）到目的结点的最短路径长度
length1=nx.dijkstra_path_length(G, 0, 4)
#使用迪杰斯特拉算法获取从源结点（source）到目的结点的最短路径
path1=nx.dijkstra_path(G, 0, 4)
#使用贝尔曼-福特算法获得从源结点（source）到目的结点的最短路径长度
length2=nx.bellman_ford_path_length(G,0,4)
#使用贝尔曼-福特算法获取从源结点（source）到目的结点的最短路径
path2=nx.bellman_ford_path(G,0,4)
#使用迪杰斯特拉算法获得每两个节点之间的最短路径长度
length3 = dict(nx.all_pairs_dijkstra_path_length(G))
#使用迪杰斯特拉算法获得每两个节点之间的最短路径
path3 = dict(nx.all_pairs_dijkstra_path(G))
（四）、实现最短路径高亮
主要步骤：
- 获取源节点到目标结点的最短路径
- 利用循环获得每一条边
- 在原图的基础上修改边的颜色，实现最短路径高亮
#实现最短路径的高亮
answer = []
for i in range(0,len(path1)-1):
answer.append((path1[i],path1[i+1]))
nx.draw_networkx_edges(G,pos,edgelist=answer,width=3.0,alpha=0.5,edge_color='y')
（五）、完整代码
主要步骤：
- 获取源节点到目标结点的最短路径
- 利用循环获得每一条边
- 在原图的基础上修改边的颜色，实现最短路径高亮
# -*- coding: utf-8 -*-
"""
Created on Thu Aug 1 11:26:04 2019
@author: lenovo
"""
import networkx as nx #内置常用的图与复杂网络分析算法
import matplotlib.pyplot as plt #使用matplotlib库进行绘图
#初始化图
s = [0,0,1,1,7,7,2,8,2,6,2,3,3,5] #源结点
t = [1,7,7,2,8,6,8,6,5,5,3,5,4,4] #目的结点
w = [4,8,3,8,1,6,2,6,4,2,7,14,9,10] #权
#无向图的构建
G = nx.Graph() #创建一个无向图
for i in range(0,len(s)): #遍历每一条边
G.add_edge(s[i], t[i], weight = w[i]) #为图G添加边，并且附上权重weight
#生成节点位置
pos=nx.spring_layout(G) #设置布局
plt.xticks([]) #取消x轴的刻度
plt.yticks([]) #取消y轴的刻度
#把节点画出来
nx.draw_networkx_nodes(G,pos,node_color='r',node_size=500,alpha=0.8) #显示每一个结点
#把边画出来
nx.draw_networkx_edges(G,pos,width=3.0,alpha=0.5,edge_color='b') #显示每一条边
#把节点的标签画出来
nx.draw_networkx_labels(G,pos,font_size=16) #显示每一个结点上的数字
#把边权重画出来
edge_labels = nx.get_edge_attributes(G,'weight') #获取每一条边的权重
nx.draw_networkx_edge_labels(G, pos, edge_labels) #为图添加上权重
def get(G):
#使用迪杰斯特拉算法获得从源结点（source）到目的结点的最短路径长度
length1=nx.dijkstra_path_length(G, 0, 4)
#使用迪杰斯特拉算法获取从源结点（source）到目的结点的最短路径
path1=nx.dijkstra_path(G, 0, 4)
#使用贝尔曼-福特算法获得从源结点（source）到目的结点的最短路径长度
length2=nx.bellman_ford_path_length(G,0,4)
#使用贝尔曼-福特算法获取从源结点（source）到目的结点的最短路径
path2=nx.bellman_ford_path(G,0,4)
#使用迪杰斯特拉算法获得每两个节点之间的最短路径长度
length3 = dict(nx.all_pairs_dijkstra_path_length(G))
#使用迪杰斯特拉算法获得每两个节点之间的最短路径
path3 = dict(nx.all_pairs_dijkstra_path(G))
#实现最短路径的高亮
answer = []
for i in range(0,len(path1)-1):
answer.append((path1[i],path1[i+1]))
nx.draw_networkx_edges(G,pos,edgelist=answer,width=3.0,alpha=0.5,edge_color='y')
get(G)
plt.show()
（六）、结果展示
在这里插入图片描述
