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).

graph.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.

Recommended Posts

Ant book in python: Sec.2-5 Dijkstra's algorithm
Ant book in python: Sec. 2-5 Graph
Algorithm in Python (Dijkstra's algorithm)
Ant book in python: Sec. 2-4, data structures
Ant book in python: Sec. 2-5 Graph (preparation)
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
Implement Dijkstra's Algorithm in python
Ant book in python: page 42 coin problem
Ant book in python: Priority queue self-implementation
Ant book in python: page 43 Interval scheduling
Ant book in python: page 49 Fence Repair
Genetic algorithm in python
Algorithm in Python (Bellman-Ford)
Ant book in python: page 47 Saruman's Army (POJ 3069)
Algorithm in Python (primality test)
Reproduce Euclidean algorithm in Python
Algorithm in Python (binary search)
[Python3] Dijkstra's algorithm with 14 lines
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Bubble Sort)
Ant book in python: page 45 Dictionary order minimum problem (POJ3617)
Implemented the algorithm of "Algorithm Picture Book" in Python3 (selection sort)
Algorithm in Python (breadth-first search, bfs)
Sorting algorithm and implementation in Python
Write A * (A-star) algorithm in Python
Develop an investment algorithm in Python 2
Algorithm in Python (depth-first search, dfs)
Implementing a simple algorithm in Python 2
Picture book data structure algorithm Python
Implementation of Dijkstra's algorithm with python
Algorithm (segment tree) in Python (practice)
Run a simple algorithm in Python
Python algorithm
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Algorithm in Python (ABC 146 C Binary Search
Ant book with python (chapter3 intermediate edition ~)
Write a simple greedy algorithm in Python
Alignment algorithm by insertion method in Python
Quadtree in Python --2
Python in optimization
CURL in python
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python