Python实现迪杰斯特拉算法和贝尔曼福特算法求解最短路径

关于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() 

(六)、结果展示


在这里插入图片描述
https://www.jianshu.com/p/204e57587bcb

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论