python路径规划问题

Zmean

数据格式：[左边点-----（长度/边id）-------右边点]，每个数据都是提供边id(绿色数字)、左边点、右边点、本条边长度。如上图数据为[（1，1，2，2），（2，2，3，3）]
问题：提供起点、若干途径点、终点。返回最短路径的边节点，其中起点终点的顺序不能变，中间的途径点优先经过谁没有要求，只要求总路径长度是最短的。
希望哪位大佬利用python能帮帮菜狗我解决这个问题，万分感谢~

jiuwuHust

直接引入个dijkstra的包完事儿

zhangwei0988

GitHub肯定有，用英文搜索下关键字试试

Lining1235600

这个还能怎么实现啊

wxy716615

属实没看懂需要表达的是什么

yhxwyzm

寻路算法？

Zmean

jiuwuHust 发表于 2024-3-14 13:27
直接引入个dijkstra的包完事儿

谢谢你~应该是我使用的问题吧，没有牵扯到途径点的时候，没有问题；但是一牵扯到途径点，就会出现问题，给的边集合，明显不是最短路径。

Zmean

zhangwei0988 发表于 2024-3-14 13:28
GitHub肯定有，用英文搜索下关键字试试

好嘞，我去瞅瞅

Zmean

yhxwyzm 发表于 2024-3-14 14:06
寻路算法？

对的对的，一个寻找最短路径的问题

黑泽心教

class Dijkstra:
    def __init__(self, graph, start, goal):
        self.graph = graph      # 邻接表
        self.start = start      # 起点
        self.goal = goal        # 终点

        self.open_list = {}     # open 表
        self.closed_list = {}   # closed 表

        self.open_list[start] = 0.0     # 将起点放入 open_list 中

        self.parent = {start: None}     # 存储节点的父子关系。键为子节点，值为父节点。方便做最后路径的回溯
        self.min_dis = None             # 最短路径的长度

    def shortest_path(self):

        while True:
            if self.open_list is None:
                print('搜索失败， 结束！')
                break
            distance, min_node = min(zip(self.open_list.values(), self.open_list.keys()))      # 取出距离最小的节点
            self.open_list.pop(min_node)                                                       # 将其从 open_list 中去除

            self.closed_list[min_node] = distance                  # 将节点加入 closed_list 中

            if min_node == self.goal:                              # 如果节点为终点
                self.min_dis = distance
                shortest_path = [self.goal]                        # 记录从终点回溯的路径
                father_node = self.parent[self.goal]
                while father_node != self.start:
                    shortest_path.append(father_node)
                    father_node = self.parent[father_node]
                shortest_path.append(self.start)
                print(shortest_path[::-1])                         # 逆序
                print('最短路径的长度为：{}'.format(self.min_dis))
                print('找到最短路径， 结束！')
                return shortest_path[::-1], self.min_dis                        # 返回最短路径和最短路径长度

            for node in self.graph[min_node].keys():               # 遍历当前节点的邻接节点
                if node not in self.closed_list.keys():            # 邻接节点不在 closed_list 中
                    if node in self.open_list.keys():              # 如果节点在 open_list 中
                        if self.graph[min_node][node] + distance < self.open_list[node]:
                            self.open_list[node] = distance + self.graph[min_node][node]         # 更新节点的值
                            self.parent[node] = min_node           # 更新继承关系
                    else:                                          # 如果节点不在 open_list 中
                        self.open_list[node] = distance + self.graph[min_node][node]             # 计算节点的值，并加入 open_list 中
                        self.parent[node] = min_node               # 更新继承关系


if __name__ == '__main__':
    g = {'1': {'2': 2, '4': 1},
         '2': {'4': 3, '5': 11},
         '3': {'1': 4, '6': 5},
         '4': {'3': 2, '6': 8, '7': 4, '5': 2},
         '5': {'7': 6},
         '7': {'6': 1}
         }
    start = '1'
    goal = '6'
    dijk = Dijkstra(g, start, goal)
    dijk.shortest_path()
-----------------------------------
python路线规划 python 路径规划算法
https://blog.51cto.com/u_13250/7042474