python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)

这篇具有很好参考价值的文章主要介绍了python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 最短路径问题

  • 最短路问题(Shortest Path Problem,SPP)是图论的一个经典问题,其目的在于寻找网络中任意两个节点间的最短路径,这里的最短可以衍生为距离最短、费用最小、时间最短等一系列度量。当前的涌现了很多最短路径的变种,如带资源约束的最短路径问题(Shortest Path Problem with Resource Constraints, SPPRC)等;

  • 数学模型
    m i n ∑ ( i , j ) ∈ A c i j x i j ∑ j ∈ V x i j − ∑ j ∈ V x j i = { − 1 , i = s 0 , i ≠ s a n d i ≠ t 1 , i = t min\sum_{(i,j)\in A}{c_{ij} x_{ij}}\\ \sum_{j \in V}x_{ij} - \sum_{j\in V}x_{ji} = \begin{cases} -1, & {i = s } \\ 0, & {i \neq s \quad and \quad i \neq t}\\ 1, & {i=t}\\ \end{cases} min(i,j)AcijxijjVxijjVxji= 1,0,1,i=si=sandi=ti=t

    • x i j x_{ij} xij: 0-1决策变量, x i j = 1 x_{ij}=1 xij=1表示经过弧 ( i , j ) (i, j) (i,j), x i j = 0 x_{ij}=0 xij=0表示不经过弧 ( i , j ) (i, j) (i,j)

    • c i j c_{ij} cij: 弧 ( i , j ) (i, j) (i,j)上的权重

    • A A A: 所有弧的集合

    • V V V: 所有点的集合

    • s , t s, t s,t :分别表示源节点和结束节点

2. 求解算法

一般使用label algorithmsolver求解最短路径问题,本文使用Dijkstra algorithm和开源的SCIP求解器分别求解SPP, 并做结果对比。

2.1 Label Algorithm

  • 标签算法是求解最短路径算法的常见算法,一般被分为两类:Label Setting Algorithm(如Dijkstra、Dial、Heap)和Label Correcting Algorithm(如Bellman-Ford、FIFO、Deque),两者都是基于动态规划的思想,且都是精确性算法,得到解一定是最优解。
  • 两者如何更新临时距离标签差异不同:Label Setting Algorithm,在每次迭代时将当前临时距离标签最小的更新为永久距离标签,直到所有的临时距离标签都更新为永久距离标签;而Label Correcting Algorithm在每次迭代时都有可能更新临时距离标签的值,直到最后一次迭代时所有的临时距离标签才成为永久距离标签;
  • 以上的差异点导致标准Label Setting Algorithm不适用含有负环网络,如果网络中有负环,可以采用Label Correcting Algorithm,如Bellman-Ford算法求解;

2.1.1 Dijkstra algorithm

Dijkstra算法本质上结合了贪心算法 + 动态规划的思想,关于其理论部分就不在此赘述,详细算法步骤见代码注释

  • Dijkstra算法是求一个特定起点到其他所有顶点的最短路径,也称为单源最短路径算法
  • 算法时间复杂度一般是 O ( n 2 ) O(n^2) O(n2)
  • Dijkstra algorithm由于属于Label Setting Algorithm,所以不适用含有负权网络

2.1.2 python代码实现Dijkstra算法

python实现Dijkstra两种方式:

  1. 简洁一点,直接使用networkx提供了dijkstra算法的接口,只要定义带权重的图结构即可
  2. 基于图结构,使用python实现算法步骤

两种方式python代码实现如下:

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import time
import pyscipopt as opt


def print_fun_run_time(func):
    def wrapper(*args, **kwargs):
        local_time = time.time()
        func(*args, **kwargs)
        print('current function [%s] run time is %.4f'%(func.__name__, time.time()-local_time))
    return wrapper


def pic_graph(Nodes, Arcs):
    """
    可视化图,节点的相对位置可能改变
    """
    np.random.seed(1)
    # 定义有向图
    Graph = nx.DiGraph()
    # 定义节点
    for node in Nodes:
        Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
    # 定义弧
    for (from_node, to_node), weight in Arcs.items():
        Graph.add_edge(from_node, to_node, weight=weight)

    plt.figure(figsize=(7, 5), dpi=100)
    pos = nx.spring_layout(Graph)

    nx.draw_networkx(Graph, pos)
    node_labels = nx.get_node_attributes(Graph, 'node_name')
    nx.draw_networkx_labels(Graph, pos, labels=node_labels)
    edge_labels = nx.get_edge_attributes(Graph, 'weight')
    nx.draw_networkx_edge_labels(Graph, pos, edge_labels=edge_labels)

    plt.savefig('./spp_grap.png')
    plt.show()

    return True


def prepare_data():
    # 测试数据: 邻接矩阵标识图结构,其中极大值1000表示不连通, 测试数据包含11个节点
    matrix = np.array([[0, 2, 8, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
                       [2, 0, 6, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000],
                       [8, 6, 0, 7, 5, 1, 2, 1000, 1000, 1000, 1000],
                       [1, 1000, 7, 0, 1000, 1000, 9, 1000, 1000, 1000, 1000],
                       [1000, 1, 5, 1000, 0, 3, 1000, 2, 1000, 1000, 1000],
                       [1000, 1000, 1, 1000, 3, 0, 4, 1000, 6, 1000, 1000],
                       [1000, 1000, 2, 9, 1000, 4, 0, 1000, 3, 1, 1000],
                       [1000, 1000, 1000, 1000, 2, 1000, 1000, 0, 7, 1000, 9],
                       [1000, 1000, 1000, 1000, 1000, 6, 3, 7, 0, 1, 2],
                       [1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1, 0, 4],
                       [1000, 1000, 1000, 1000, 1000, 1000, 1000, 9, 2, 4, 0]])

    # 转换数据(只是为了方便理解,不为效率), 获取不包含本节点且连通的点及弧
    row, col = np.where((matrix != 1000) & (matrix != 0))
    Nodes = list(np.unique(np.unique(np.append(row, col)) + 1).astype('str'))
    Arcs = {}
    for i in range(len(row)):
        Arcs[str(row[i] + 1), str(col[i] + 1)] = matrix[row[i], col[i]]
    print('Nodes:\n', Nodes)
    print('Arcs:\n', Arcs)
    return Nodes, Arcs

@print_fun_run_time
def networkx_dijkstra(Nodes, Arcs, source, target):
    """
    networkx提供了dijkstra算法的方法的封装,只要定义图结构即可。感兴趣可以学一下networkx的源码。
    """
    Graph = nx.DiGraph()
    # 添加节点
    for node in Nodes:
        Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
    # 添加带权重的边
    for (from_node, to_node), weight in Arcs.items():
        Graph.add_weighted_edges_from([(from_node, to_node, weight)])

    path = nx.dijkstra_path(Graph, source=source, target=target)
    distance = nx.dijkstra_path_length(Graph, source=source, target=target)
    print(f'节点 {source}{target} 的路径={path}, 最短距离={distance}')

    return True


@print_fun_run_time
def Dijkstra(Nodes, Arcs, source, target):
    """
    Parameters
    ----------
    Nodes: list
        the set of node

    Arcs: dict
        key: pairs of node (from node, end node)
        value: weight

    source : node
        Starting node

    target : node
        Ending node

    Returns
    -------
    path : list
        List of nodes in the shortest path
    distance: Float
        The short distance from source to target
    """
    # ========== 数据结构 ==========
    # 定义有向图
    Graph = nx.DiGraph()
    # 定义节点
    for node in Nodes:
        Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
    # 定义弧
    for (from_node, to_node), weight in Arcs.items():
        Graph.add_edge(from_node, to_node, weight=weight)

    # ========== 算法开始 ==========
    # 初始化未探索节点集合: 初始时为所有节点集合
    tmp_set = list(Graph.nodes())

    # 初始化当前节点及所有节点的最短距离:起始点作为当前节点,并将起始点的最短路径置为0,其他节点距离置为无穷大
    current_node = source
    for node in tmp_set:
        if (node == source):
            Graph.nodes[node]['min_dis'] = 0
        else:
            Graph.nodes[node]['min_dis'] = np.inf

    # 算法终止条件: 所有节点均被探索
    while (len(tmp_set) > 0):
        # 选择未探索的节点中的最短路径的节点作为新的当前节点
        min_dis = np.inf
        for node in tmp_set:
            if (Graph.nodes[node]['min_dis'] < min_dis):
                current_node = node
                min_dis = Graph.nodes[node]['min_dis']

        # 删除已探索的节点
        if (current_node != None):
            tmp_set.remove(current_node)

        """
        循环判断当前节点所有相邻的节点:
        1. 计算当前节点的最小值 + 相邻节点的权重的和,
        2. 若小于相邻节点的最小距离,则更新相邻节点的最小距离,并标记相邻节点的前一个节点为当前节点
        """
        for neighbor_node in Graph.successors(current_node):
            arc = (current_node, neighbor_node)
            dis_t = Graph.nodes[current_node]['min_dis'] + Graph.edges[arc]['weight']
            if (dis_t < Graph.nodes[neighbor_node]['min_dis']):
                Graph.nodes[neighbor_node]['min_dis'] = dis_t
                Graph.nodes[neighbor_node]['previous_node'] = current_node

    # ========== 获取结果 ==========
    """
    获取结果: 
    1. 结束节点上更新的最短距离即为整个最短路径的距离
    2. 根据结束节点回溯, 依次找到其上一个节点
    """
    distance = Graph.nodes[target]['min_dis']
    current_node = target
    path = [current_node]
    while (current_node != source):
        current_node = Graph.nodes[current_node]['previous_node']
        path.insert(0, current_node)

    print(f'节点 {source}{target} 的路径={path}, 最短距离={distance}')
    return True


if __name__ == '__main__':
    source = '1'  # starting node
    target = '11'  # ending node
    # 测试数据
    Nodes, Arcs = prepare_data()
    # 可视化图
    pic_graph(Nodes, Arcs)
    # 方式1: 使用networkx提供了dijkstra算法的方法的封装
    networkx_dijkstra(Nodes, Arcs, source, target)
    # 方式2: python实现Dijkstra算法求解最短路径问题
    Dijkstra(Nodes, Arcs, source, target)

2.2 python调用SCIP求解器求解最短路径问题

代码实现可见之前写的博客 python调用求解器SCIP求解最短路径问题(Shortest Path Problem)

3. 算法结果

python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)
python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)


参考文献

Dijkstra E W . A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematics, 1959.

Martins E . On a multicriteria shortest path problem[J]. European Journal of Operational Research, 1984, 16(2):236-245.文章来源地址https://www.toymoban.com/news/detail-491605.html

到了这里,关于python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

    最短路径的算法有两个, Dijkstra算法 和 Floyd算法 。 Dijkstra算法 解决的是 单源 最短路径问题 。 Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图 。 今天要讲的就是Dijkstra算法。 加: feng--Insist (大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 其他资料

    2024年02月11日
    浏览(58)
  • 数据结构(12)Dijkstra算法JAVA版:图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径,即最少步数,使用BFS+贪心算法来求解最短路径,比较好实现,此处不做展开讨论。 有权图的最短路径,不考虑权重为负数的情况,因为权重为负

    2024年02月06日
    浏览(48)
  • Dijkstra’s 最短路径算法的 Matlab实现

    随机生成400个点,再去除其中的120个点作为‘路障’。采用dijkstra算法寻找最短路径。   思路: step1:定义地图大小/内容 step2:把随机生成的‘视觉地图’信息载入‘矩阵地图’ step3:使用dijkstra原理寻找最短路径 step4:连点成线 把 ‘视觉地图’ 信息载入矩阵的原理/逻辑

    2024年02月07日
    浏览(42)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(59)
  • Floyd算法求解各顶点之间最短路径问题

    一、Floyd算法 概述 Floyd算法,也称为Floyd-Warshall算法,是一种用于求解图中所有节点之间最短路径的算法。Floyd算法可以处理负权边的情况,但是不能处理负权环。 Floyd算法基于动态规划思想,通过一个二维数组记录从一个节点到另一个节点的最短路径长度。算法的核心思想是

    2024年02月05日
    浏览(43)
  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(39)
  • 使用邻接矩阵实现有向图最短路径Dijkstra算法 题目编号:1136

    用邻接矩阵存储有向图,实现最短路径Dijkstra算法,图中边的权值为整型,顶点个数少于10个。 部分代码提示: #include #include using namespace std; const int MaxSize = 10; const int INF = 32767; class MGraph { public: MGraph(char a[], int n, int e); private: char vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum,

    2024年02月01日
    浏览(80)
  • 广度优先搜索(BFS)算法求解单源最短路径问题

      单源最短路径问题是图论中一类重要且常见的应用问题。在这个问题中,我们需要找到从一个给定源节点到其他节点的最短路径。广度优先搜索(BFS)算法是一种常用且有效的求解这一问题的算法。   本篇博客将重点讨论单源最短路径问题及其实际应用,同时简要介绍

    2024年02月13日
    浏览(46)
  • 【数据结构】最短路径算法实现(Dijkstra(迪克斯特拉),FloydWarshall(弗洛伊德) )

    最短路径问题 :从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径 针对一个带权

    2024年02月04日
    浏览(50)
  • Dijkstra算法实现求有向图中一顶点到其余各个顶点的最短路径

    一、文章说明: C++语言实现; 有向图的存储结构为: 邻接矩阵; 这篇文章的代码是我根据B站UP主 懒猫老师 所写的,能成功运行,VS里面显示有很多警告。而且还可能存在有未调试出的BUG,请多多指教。 观看懒猫老师的视频后,才方便理解博主代码,不然可能理解起来会很吃

    2024年02月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包