Блог

Главная - Вопросы по программированию - Как вычислить сумму веса пути в Python

Как вычислить сумму веса пути в Python

#python #data-structures

#python #структуры данных

Вопрос:

Как мне вычислить ребро? Например (посмотрите изображение): я начал в городе Боджонсоанг, и пункт назначения, в который я направляюсь, — это Dago, тогда результат вычисления ребра должен быть 220.

ИЗОБРАЖЕНИЕ

 class Graph:
      def __init__(self):
        self.graph = {}
        self.vertices_no = 0

      def insertVertex(self,vertex):
        if vertex in self.graph:
          print("Vertex in Graph")
        else:
          self.graph[vertex] = []
          self.vertices_no =1

      def insertEdge(self,vertex1,vertex2, distance):
        if vertex1 not in self.graph:
          print("vertex not in Graph")
        elif vertex2 not in self.graph:
          print("vertex not in Graph")
        else:
          temp = [vertex2, distance]
          self.graph[vertex1].append(temp)
  
      def printGraph(self):
        for vertex in self.graph:
          for edge in self.graph[vertex]:
            print(vertex, "-> ", edge[0], " Distance: ", edge[1])

Комментарии:

1. Вы хотите вычислить расстояние между вершинами, учитывая список вершин между ними, или вы хотите вычислить кратчайший путь между двумя вершинами?

2. я хочу рассчитать расстояние между двумя вершинами

3. Вопрос в том, указываете ли вы весь путь или только начальную и конечную точки? Ваш пример предлагает целый путь, поскольку существует более короткий маршрут от Аркаманика до Даго через Чумбулейт, но вы, похоже, хотите более длинный маршрут через Боджонсоанг.

4. я имею в виду опечатку от «Arcamanik» до «Dago»

Ответ №1:

Если вы хотите вычислить кратчайшее расстояние между двумя вершинами, взгляните на алгоритм Дейкстры: https://en.wikipedia.org/wiki/Dijkstra’s_algorithm .

Если вы просто хотите вычислить расстояние между двумя вершинами, учитывая список вершин, попробуйте что-то вроде этого (еще не протестировано и не так чисто, как могло бы быть …):

 def calculateDistance(self, vertices):
    distance = 0
    if len(vertices) == 0 or len(vertices) == 1:
        return distance
    
    for i in range(0, len(vertices) - 1):
        changed = False
        for v in self.graph[vertices[i]]:
            if v[0] == vertices[i   1]:
                distance  = v[1]
                changed = True
                break
        if not changed:
            raise ArgumentError("vertex doesn't exist in graph")
    return distance

temp Я думаю, что попытка изменения в insertEdge словаре упростит задачу.

Метки: