Implementation of Dijkstra's algorithm with python

Introduction

I implemented Dijkstra's algorithm in python. I'm not used to posting, but I intend to write it as clearly as possible (a lie)

Having recently studied graph theory at university, I suddenly wanted to find the shortest path lol The code is dirty, but I hope it helps someone!

What is Dijkstra's algorithm?

Dijkstra's algorithm is an algorithm that finds the "minimum weight path". The basic idea of Dijkstra's algorithm is as follows.

1. Divide the route with the smallest weight that has been searched for vertices into a confirmed part and an undetermined part.
2. Update the route to the undetermined part using the value of the edge between the confirmed part.
3. Increase the vertices of the path with the smallest weight that has been determined sequentially one by one.
4. Perform the above operations until you know the shortest distances of all vertices.

If you don't know what you're talking about, I recommend watching the video below! Explanation of Dijkstra's algorithm of Yobinori

Tried to make it

I will introduce the code at once.

dijkstra.py

import heapq
class Map:  #Define Map class
    def __init__(self,start,goal):
        self.__start = start
        self.__goal = goal
        self.v_list =[] #[(0,s),(1,a)](weight,label) 
        self.e_list = {}  #Edge dictionary
        self.dic_v_list = []
        self.dic_e_list ={}

    #Initialize
    def add_list(self,cross_streets,load):
        for i in range(len(cross_streets)):
            if cross_streets[i]==self.__start:
                self.v_list.append((0,cross_streets[i]))
            else:
                self.v_list.append((float('inf'),cross_streets[i])) #float('inf')Is infinite(∞,'a')
        
        if self.__start <= self.__goal:
            self.e_list = load
        else:
            #(1,2):If there is 5(2,1):Add 5 to the dictionary
            for ld in load:
                self.e_list.update({(ld[1],ld[0]):load[ld]})
    
    #Function to add a way
    def load_add(self,weight,label): 
        #Determine if it is a start
        if weight != 0:
            #Find the same path as the label ex. label:2→(1,2,4)
            loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k2 ==label]
            #Find all paths that contain the specified label
            for load in loads:
                #Find the corresponding vertex and calculate the new weight
                for (v0,v1) in [(v0,v1) for (v0,v1) in self.dic_v_list if v1==load[0]]:
                        #Determine if the argument weight is equal to the path + vertex weight
                        if weight == v0+load[2]:
                            self.dic_e_list.update([((load[0],load[1]),load[2])])

    #Follow the path in reverse
    def back_calculation(self):
        #Substitute goal
        label=[self.__goal]
        #Follow the path from goal to start
        while label[len(label)-1] != self.__start:
            load = [(k1,k2,val) for (k1,k2), val in self.dic_e_list.items() if k2 == label[len(label)-1]] #k is, for example, s,a,b
            label.append(load[0][0])
        return label

    def dijkstra(self):
        #Loop until there are no vertices
        while len(self.v_list) > 0:
            #Find the minimum
            heapq.heapify(self.v_list)
            (weight, label) = heapq.heappop(self.v_list)

            #Seeking an adjacent road
            loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k1 == label]

            for load in loads:
                #Find matching weights in a list of pairs
                for (v0,v1) in [(v0,v1) for (v0,v1) in self.v_list if v1==load[1]]:   
                        #Update weights
                        if weight + load[2] <= v0:
                            list_count = self.v_list.index((v0,v1)) #Substitute the element number of the list
                            self.v_list[list_count] = (weight + load[2],v1)
            #Added fixed vertices and paths
            self.dic_v_list.append((weight,label))
            self.load_add(weight,label)

    def serach(self):
        self.dijkstra()
        return self.back_calculation()

cross_streets = [1,2,3,4,5,6,7,8]  #All intersections(vertex)List of
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #All roads(Edge)Dictionary
map = Map(7,1)  #Create a Map instance
map.add_list(cross_streets,load) #Make a map
print(map.serach())

Commentary

* Only important parts will be explained.

v_list is a tuple type list of labels and vertices, and e_list is a dictionary type of edges. (For example, if the length of the side between s-t is 10, it is expressed as {(s, t): 10}) dic_v_list and dic_e_list store vertices and edges with fixed minimum weight distances.

class Map:  #Define Map class
    def __init__(self,start,goal):
        self.__start = start
        self.__goal = goal
        self.v_list =[] #[(0,s),(1,a)](label,vertex) 
        self.e_list = {}  #Edge dictionary
        self.dic_v_list = []
        self.dic_e_list ={}

The vertices and paths are passed as follows:

cross_streets = [1,2,3,4,5,6,7,8]  #All intersections(vertex)List of
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #All roads(Edge)Dictionary
map = Map(7,1)

This is the function that finds the most important path with the least weight in this program. The flow is as follows. ⑴ Use heapq to find the vertex with the smallest weight. Then take it out with heapq.pop. ⑵ Store the side extending from the extracted vertex in load as a list type. (3) Compare the weights of the vertices connected to each side, and update if the weights can be updated. (4) Add the confirmed vertices and edges to dic_v_list and dic_e_list.

In other words, this function is responsible for "finding the vertices with the least weight" and "updating the weights of adjacent vertices".

    def dijkstra(self):
        #Loop until there are no vertices
        while len(self.v_list) > 0:
            #Find the minimum
            heapq.heapify(self.v_list)
            (weight, label) = heapq.heappop(self.v_list)

            #Seeking an adjacent road
            loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k1 == label]

            for load in loads:
                #Find matching weights in a list of pairs
                for (v0,v1) in [(v0,v1) for (v0,v1) in self.v_list if v1==load[1]]:   
                        #Update weights
                        if weight + load[2] <= v0:
                            list_count = self.v_list.index((v0,v1)) #Substitute the element number of the list
                            self.v_list[list_count] = (weight + load[2],v1)
            #Added fixed vertices and paths
            self.dic_v_list.append((weight,label))
            self.load_add(weight,label)

The rest are all extra functions. (Omit explanation)

Execution result

Try it with the following graph.

They are arranged in order from goal to start, but you have successfully executed the answer.

#original data:Start 7,Goal 1
cross_streets = [1,2,3,4,5,6,7,8]  #All intersections(vertex)List of
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #All roads(Edge)Dictionary
map = Map(7,1)
#Execution result
[1, 3, 5, 7]

#Of course it holds even if it is reversed
cross_streets = [1,2,3,4,5,6,7,8]  #All intersections(vertex)List of
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #All roads(Edge)Dictionary
map = Map(1,7)
#Execution result
[7, 5, 3, 1]