Dijkstra'nın algoritmasının uygulanmasında çözülmemiş bir zorlukla ilgili yardım aranıyor.

[Timothycarl]

Şu anda ağırlıklı bir grafik için Dijkstra'nın yöntemini uygulamaya çalışıyorum, ancak bir hatayı çözmekte zorlanıyorum. Prosedürün aşamalarını takip etmesine rağmen, algoritma sonsuz bir döngüye giriyor ve sonlanmıyor.

İşte mesafeleri değiştiren bir kod parçası:

while len(unvisited_nodes) > 0:
    current_node = min(unvisited_nodes, key=lambda node: distances[node])
    unvisited_nodes.remove(current_node)
    
    for neighbor in graph[current_node]:
        new_distance = distances[current_node] + graph[current_node][neighbor]
        if new_distance < distances[neighbor]:
            distances[neighbor] = new_distance
            unvisited_nodes.append(neighbor)

Kenar ağırlıklarının negatif olmadığından emin olmak için kodu ve grafik temsilimi iki kez kontrol ettim. Ancak algoritmayı çalıştırdığımda, düğümleri tekrar ziyaret ediyor gibi görünüyor ve belirsiz bir döngüye giriyor.

Linki görebilmek için üye olmanız gerekiyor. Giriş yap veya üye ol.

blogunu okudum ve mesafeler dizisini güncellemem veya unvisited_nodes listesini korumamla ilgili bir sorun olduğunu düşünüyorum. Görünüşe göre, mesafeleri doğru bir şekilde düzeltilmiş olsa bile, düğümler tekrar listeye ekleniyor.

Verilen kodda sonsuz döngüyü oluşturabilecek herhangi bir hata tespit edebiliyor musunuz? Bu sorunun nasıl aşılacağına dair herhangi bir fikir ve öneri çok takdir edilecektir. Yardımınız için şimdiden teşekkür ederim!"