求出最短路径，要过程，用Dijkstra算法。。。

2025-03-25 16:23:01

推荐回答（2个）

回答1：

从v1开始遍历
v2 = 2;
v3 = 5;
v2较小所以跳到v2
v3 = 4;

v4 = 6;
v5 = 8;
v3较小所以跳到v3
v4 = 5;
v6 = 7;
v4较小所以跳到v4
v6 = 6;
v7 = 9;
v6较小所以跳到v6
v7 = 8;

所以最后结果v1 -> v7最短路径为v1->v2->v3->v4->v6->v7,最短路径长度为8

回答2：

# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""
#import collections
import heapq

#==============================================================================
# class Graph:
#     def __init__(self):
#         self.edges = {}
#
#     def neighbors(self,id):
#         return self.edges[id]
#==============================================================================

#   原型
class GraphWithWeights():
    def __init__(self):
        #super.__init__(self)
        self.edges_weights = {}
    def cost(self, from_node, to_node):
        return self.edges_weights.get(from_node).get(to_node)
    def neighbors(self,node):
        return list(self.edges_weights.get(node).keys())

class PriorityQueue:
    def __init__(self):
        self.elements = []
#   检查优先序列是否为空
    def empty(self):
        return len(self.elements) == 0
#   依据优先权重添加一个成员
    def put(self, item, priority):
        heapq.heappush(self.elements, (priority, item))
#   取出成员
    def get(self):
        return heapq.heappop(self.elements)[1]

#   根据图设置值，顶点，边，权重，
target_graph = GraphWithWeights()
target_graph.edges_weights = {
    'V1':{'V2':2, 'V3':5},
    'V2':{'V1':2, 'V3':2, 'V4':4, 'V5':6},
    'V3':{'V1':5, 'V2':2, 'V4':1, 'V6':3},
    'V4':{'V2':4, 'V3':1, 'V5':4, 'V6':1,'V7':4},
    'V5':{'V2':6, 'V4':4, 'V7':1},
    'V6':{'V3':3, 'V4':1, 'V7':2},
    'V7':{'V4':4, 'V5':1, 'V6':2}
}

#   dijkstra 算法
def dijkstra_search(graph, start, goal):
    #pass
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    came_from[start] = None
    cost_so_far = {}
    cost_so_far[start] = 0

    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break
        for next in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current,next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next]=new_cost
                priority = new_cost
                frontier.put(next, priority)
                came_from[next] = current
    return came_from, cost_so_far

def reconstruct_path(came_from, start, goal):
    current = goal
    path = [current]
    while current != start:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

c, f = dijkstra_search(target_graph, 'V1', 'V7')
path=reconstruct_path(c,'V1','V7')
print("最短路径为：{}".format(path))
#==============================================================================
# 最短路径为：['V1', 'V2', 'V3', 'V4', 'V6', 'V7']
#==============================================================================

最新问答

常用的焊接工具有哪些焊接

不是说太空是真空的吗，没有空气，为什么太阳还能燃烧

十幅对联点醒众生，时时感悟通透人生

女1980年农历7月3日出生是什么命？

我有一件紫色衣服，洗了后，发黄，怎么洗也洗不掉，怎么办

天津西站现在开了吗，我买的4412车的票，凌晨一点到天津西，问一下修好了吗？

2010.11.28日农行卡里面的钱全被人取光了，卡号跟密码都没有告诉过别人，深圳公明这边有谁也被盗了？

杯具一词的来源及含义拜托各位大神

尊敬的客户:欢迎参加三星及以上客户流量充值送50元3GB优惠活动,您已成功充值5

南阳市社旗县唐庄乡初级中学几月几日开学?