Ant book in python: Sec.2-5 Dijkstra's algorithm

Dijkstra's algorithm is a solution to the problem of finding the minimum distance between two points on a given weighted undirected graph, and is ok unless there is a negatively weighted edge.

I was afraid when I read the explanation, but as a result of thinking about an implementation that creates another graph as shown below, I fell in love with it.

For implementation, the following method was added to the weighted graph class. As an operation

1. Remove the edge from from_node to to_node
2. If from_node floats in 1, remove from_node from the graph

    def remove_wo_weight(self, from_node, to_node):

        if from_node in self:
            count = 0
            for [node, weight] in self[from_node]:
                if node == to_node:
                    self[from_node].pop(count)
                count += 1

            if self[from_node] == []:

                self.pop(from_node)

The code for Dijkstra's algorithm is below.

import mygraph

print("number of nodes")
N = int(input())

print("input graph")
graph = mygraph.WeightedGraph()

while 1:

    inputline = input()

    if inputline == "":
        break

    inputline = list(map(int, inputline.split()))

    graph.join(inputline[0], inputline[1], inputline[2])

graph = graph.undirected()


for node in graph:
    if not isinstance(graph[node][0], list):
        graph[node] = [graph[node]]

print("Start?")
startpos = int(input())
print("Goal?")
goalpos = int(input())


dp = N * [float("INF")]

minlength_graph = mygraph.WeightedGraph()

minlength_graph.join(startpos, startpos, 0)


while 1:

    shortest_comb = [0, 0, float("INF")]

    for min_node in minlength_graph:

        for [to_node, to_weight] in graph[min_node]:

            if shortest_comb[2] > minlength_graph.weight(startpos, min_node) + to_weight:

                shortest_comb = [min_node, to_node, minlength_graph.weight(
                    startpos, min_node) + to_weight]

    minlength_graph.join(startpos, shortest_comb[1], shortest_comb[2])

    for fixed_nodes in minlength_graph:

        graph.remove_wo_weight(fixed_nodes, shortest_comb[1])

        graph.remove_wo_weight(shortest_comb[1], fixed_nodes)

    if shortest_comb[1] == goalpos:

        print(shortest_comb[2])

        break

    minlength_graph = minlength_graph.undirected()

Input and output omitted (same as Bellman Ford)

Create a graph = minlength_graph that connects the points where the initial position and distance are fixed, and the distance to that point as weight, and delete the edges between nodes included in minlength_graph from the original graph with graph.remove_wo_weight (). I will go.

In short, it just makes minlength_graph act as a dp list, but I feel that it has become easier to understand visually (?) (Hereafter gif).

Postscript) Considering the amount of calculation, it is better to record not only the node with the shortest distance but also the node closest to the second. Then, in the next step, it is sufficient to compare only the distance to the point adjacent to the point where the distance is newly determined and the distance to the second shortest point in the previous step, so that there is no waste.