Find the shortest path with the Python Dijkstra's algorithm

Shortest path problem [Dijkstra's algorithm](https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83% 88% E3% 83% A9% E6% B3% 95) is used for the solution.

(About Dijkstra's algorithm from Wikipedia)
Dijkstra's algorithm (Dijkstra's algorithm, English: Dijkstra's algorithm) is in graph theory
This is a best-first search algorithm for solving the single starting point shortest path problem when the edge weights are non-negative.
Bellman if edge weights contain negative numbers-Ford method etc. can be used. If all edge weights are the same non-negative number
Breadth-first search is fast, and the shortest path can be calculated in linear time.
Also, if the edge weight is a positive integer in an undirected graph, the Thorup algorithm is used.
It is possible to calculate in linear time, but it is not very practical.

Dijkstra's algorithm searches each node in ascending order of distance from "node 1", and searches for the shortest distance of a specific node. In terms of narrowing down the candidates, the branch and bound method used in Solving the Python knapsack problem with the branch and bound method I had a similar feeling.

We would appreciate it if you could let us know if there are any deficiencies or suggestions for improvement regarding the code.

problem

There are the following routes. There are 5 nodes from 1 to 5, and the number on the route is the required time. Find the shortest path from "node 1" to "node 5".

dikstra.png

answer

import math

route_list = [[0, 50, 80, 0, 0], [0, 0, 20, 15, 0 ], [0, 0, 0, 10, 15], [0, 0, 0, 0, 30], [0, 0, 0, 0, 0]] #List of distances between initial nodes

node_num = len(route_list) #Number of nodes

unsearched_nodes = list(range(node_num)) #Unsearched node
distance = [math.inf] * node_num #List of distances per node
previous_nodes = [-1] * node_num #A list of nodes that arrive immediately before that node on the shortest path
distance[0] = 0 #The initial node distance is 0

# @Addition of function from GDaigo's comment 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #Repeat until there are no unsearched nodes
    #First, select the unsearched node with the smallest distance.
    posible_min_distance = math.inf #Temporary distance to find the smallest distance. The initial value is set to inf.
    for node_index in unsearched_nodes: #Loop of unsearched nodes
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] #Update if smaller value is found
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) #Get the lowest index number of unsearched nodes
    unsearched_nodes.remove(target_min_index) #Removed from unsearched list as it searches here

    target_edge = route_list[target_min_index] #List of edges extending from the target node
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis #Update distance if less than previously set distance
                previous_nodes[index] =  target_min_index #Also updated the list of nodes that arrived immediately before

#View results below

print("-----Route-----")
previous_node = node_num - 1
while previous_node != -1:
    if previous_node !=0:
        print(str(previous_node + 1) + " <- ", end='')
    else:
        print(str(previous_node + 1))
    previous_node = previous_nodes[previous_node]

print("-----distance-----")
print(distance[node_num - 1])

result

-----Route-----
5 <- 3 <- 2 <- 1
-----distance-----
85

Recommended Posts

Find the shortest path with the Python Dijkstra's algorithm
[Introduction to Algorithm] Find the shortest path [Python3]
[Python3] Dijkstra's algorithm with 14 lines
Calculate the shortest route of a graph with Dijkstra's algorithm and Python
Find the Levenshtein Distance with python
Implementation of Dijkstra's algorithm with python
Search the maze with the python A * algorithm
Try to solve the shortest path with Python + NetworkX + social data
Find the maximum Python
Find the mood value with python (Rike Koi)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
Algorithm in Python (Dijkstra's algorithm)
Solving the Python knapsack problem with the greedy algorithm
The first algorithm to learn with Python: FizzBuzz problem
Find the difference in Python
Implement Dijkstra's Algorithm in python
Call the API with python3.
Find the maximum python (improved)
Solve the spiral book (algorithm and data structure) with python!
[Python] Get the script execution directory with an absolute path
Extract the xz file with python
[Python] Find the second smallest value.
Get the desktop path in Python
Get the weather with Python requests
Get the weather with Python requests 2
Get the script path in Python
First OSMnx ~ With shortest path search ~
Install the Python plugin with Netbeans 8.0.2
I liked the tweet with python. ..
Get the desktop path in Python
Master the type with Python [Python 3.9 compatible]
Find the optimal value of a function with a genetic algorithm (Part 2)
[ffmpeg] After ffmpeg using Python subprocess, The system cannot find the path specified.
Make the Python console covered with UNKO
Find the maximum value python (fixed ver)
Algorithm learned with Python 10th: Binary search
Algorithm learned with Python 5th: Fibonacci sequence
[Python] Set the graph range with matplotlib
Implement the shortest path search for the maze
Algorithm learned with Python 9th: Linear search
Compute the partition function with the sum-product algorithm
Behind the flyer: Using Docker with Python
Ant book in python: Sec.2-5 Dijkstra's algorithm
Pass the path of the imported python module
Algorithm learned with Python 7th: Year conversion
Try the Variational-Quantum-Eigensolver (VQE) algorithm with Blueqat
Check the existence of the file with python
Algorithm learned with Python 8th: Evaluation of algorithm
Find the SHA256 value with R (with bonus)
[Python] Get the variable name with str
[Python] Round up with just the operator
Display Python 3 in the browser with MAMP
Python algorithm
Algorithm learned with Python 4th: Prime numbers
Let's read the RINEX file with Python ①
Working with OpenStack using the Python SDK
Algorithm learned with Python 2nd: Vending machine
Algorithm learned with Python 19th: Sorting (heapsort)
Download files on the web with Python
Check the path of the Python imported module
Find the general terms of the Tribonacci sequence with linear algebra and Python