Алгоритм Дейкстры - Python - Ответ 11918024

dmake · 06.12.2017, 14:34 **[ТС]**

Сообщение от Vigi

на глаз в 4, 20 строке ошибка и лишние отступы после 42

Поправил отступы и пошли ошибки. Компилятор указывает на 20 строку, но что не так? Ведь я множеству Graph.nodes, которое ранее обозначил частью Графа в строчке 4 присваиваю значение nodes. Что не так?

Python

from collections import defaultdict
 
class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = defaultdict(list)
        self.distances = {}
 
    def add_node(self, value):
        self.nodes.add(value)
 
    def add_edge(self, from_node, to_node, distance):
        self.edges[from_node].append(to_node)
        self.distances[(from_node, to_node)] = distance
 
def dijkstra(graph, initial):
    visited = {initial: 0}
    path = defaultdict(list)
 
    nodes = set(Graph.nodes)
 
    while nodes:
        min_node = None
        for node in nodes:
            if node in visited:
                if min_node is None:
                    min_node = node
                elif visited[node] < visited[min_node]:
                    min_node = node
 
        if min_node is None:
            break
 
        nodes.remove(min_node)
        current_weight = visited[min_node]
 
        for edge in graph.edges[min_node]:
            weight = current_weight + graph.distances[(min_node, edge)]
            if edge not in visited or weight < visited[edge]:
                visited[edge] = weight
                path[edge].append(min_node)
 
g = Graph()
g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_node('D')
g.add_node('E')
g.add_node('F')
g.add_node('G')
g.add_edge('A','B',12)
g.add_edge('A','C',7)
g.add_edge('B','D',1)
g.add_edge('B','A',12)
g.add_edge('D','E',8)
g.add_edge('C','F',3)
g.add_edge('D','G',5)
g.add_edge('F','B',1)
g.add_edge('F','G',2)
g.add_edge('C','D',13)
g.add_edge('E','B',6)
print(dijkstra(g, 'A')['B'])

Добавлено через 33 минуты
Поковырялся еще немного, теперь выпадает ошибка: TypeError: 'NoneType' object is not subscriptable к 65 строке.
Вот код:

Python

from collections import defaultdict
 
 
class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = defaultdict(list)
        self.distances = {}
 
    def add_node(self, value):
        self.nodes.add(value)
 
    def add_edge(self, from_node, to_node, distance):
        self.edges[from_node].append(to_node)
        self.distances[(from_node, to_node)] = distance
 
 
def dijkstra(Graph, initial):
    visited = {initial: 0}
    path = defaultdict(list)
 
    nodes = set(Graph.nodes)
 
    while nodes:
        min_node = None
        for node in nodes:
            if node in visited:
                if min_node is None:
                    min_node = node
                elif visited[node] < visited[min_node]:
                    min_node = node
 
        if min_node is None:
            break
 
        nodes.remove(min_node)
        current_weight = visited[min_node]
 
        for edge in Graph.edges[min_node]:
            weight = current_weight + Graph.distances[(min_node, edge)]
            if edge not in visited or weight < visited[edge]:
                visited[edge] = weight
                path[edge].append(min_node)
 
 
g = Graph()
g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_node('D')
g.add_node('E')
g.add_node('F')
g.add_node('G')
g.add_edge('A', 'B', 12)
g.add_edge('A', 'C', 7)
g.add_edge('B', 'D', 1)
g.add_edge('B', 'A', 12)
g.add_edge('D', 'E', 8)
g.add_edge('C', 'F', 3)
g.add_edge('D', 'G', 5)
g.add_edge('F', 'B', 1)
g.add_edge('F', 'G', 2)
g.add_edge('C', 'D', 13)
g.add_edge('E', 'B', 6)
print(dijkstra(g, 'A')['C'])

Ошибка в последней строчке. Глаз уже замылен - подскажите пожалуйста, что делаю не так

.

Вернуться к обсуждению:
Алгоритм Дейкстры Python

Следующий ответ

Другие темы раздела
Python Список, состоящий из 10 элементов, разделить по условию Объясните новичку как это написать? Просьба написать на phyton Ввести с клавиатуры список, состоящий из 10 элементов и записать в новый список сначала все элементы кратные 5, а затем все оставшиеся.... https://www.cyberforum.ru/ python-beginners/ thread2150772.html	Сократить файл до 50 целых чисел Python File31. Дан файл целых чисел, содержащий более 50 элементов. Уменьшить его размер до 50 элементов, удалив из файла необходимое количество начальных элементов.
Python Программа, отыскивающая наименьший общий составной делитель Составьте программу, отыскивающую наименьший общий составной делитель натуральных чисел N и P https://www.cyberforum.ru/ python-beginners/ thread2150434.html	Python Подсчитать число вхождений в файл сочетаний ab https://www.cyberforum.ru/ python-beginners/ thread2150401.html Дан символьный файл f. Подсчитать число вхождений в файл сочетаний ab. Нужно попытаться сделать с помощью циклов.
Найти наибольшее целое к Python Дано положительное число с. Для каждого значения х=2,3,4,…,7 найти такое наибольшее целое к, при котором хк не превышает заданное с. Заранее спасибо!!!	Python Вычислить и вывести n членов арифметической прогрессии https://www.cyberforum.ru/ python-beginners/ thread2150395.html Вычислить и вывести n членов арифметической прогрессии с первым членом а и разностью прогрессии р. Определить их произведение. Заранее спасибо!!!
Python Все ли цифры данного числа различны https://www.cyberforum.ru/ python-beginners/ thread2150353.html Составить программу, позволяющую проверить все ли цифры натурального числа М различны.	Python Все цифры числа, начиная с первой Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой Пример: Введите натуральное число: 1234 1 2 3 4
Python Несостыковка с сохранением последовательности бит в файл в коде Хаффмена Имеется бинарный файл, в нем список чисел по 8 бит (np.int8) Они делятся на 2 части по 4 бита Эти части кодируются по Хаффмену Тут самое интересное: Нужно сохранить данные в виде... https://www.cyberforum.ru/ python-beginners/ thread2150210.html	Python Разбивка строки на массив чисел https://www.cyberforum.ru/ python-beginners/ thread2149997.html Добрый день! Только начал осваивать Пайтон, возникли 2 вопроса, на который пока не могу найти ответа. Делаю запрос к MySQL, получаю в ответ строку, состоящую из двух чисел с плавающей запятой в...
Python Вычислить сумму тех вводимых чисел, у которых первая цифра равна последней День добрый) В программе использовать циклы while или конструкцию “цикл в цикле”. На экран выводить исходные данные и результат. Использовать форматный вывод. Ни в одной из программ массивы не...	Python Как сделать по разрядную проверку? Как сделать поразрядное вычитание и проверку? Пример Есть файл examples.txt с текстом 21345 64355 67855 34522 Также есть число в переменной 68855 https://www.cyberforum.ru/ python-beginners/ thread2149750.html