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

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

Find the shortest path with the Python Dijkstra's algorithm

problem

answer

result