다익스트라 최단경로 알고리즘

class graph:
    def __init__(self):
        self.vertexList = set()
        self.edgeList = []
        self.weightList = {}  # {(start, end), weight}
        self.adjacencyList = {}
 
    def addVertex(self, vertex):
        self.vertexList.add(vertex)
 
    def addEdge(self, start, end, weight):
        self.edgeList.append((start, end))
        self.edgeList.append((end, start))
        self.weightList[(start, end)] = weight
        self.weightList[(end, start)] = weight
    
    def make_adjacencyList(self):
        for vertex in self.vertexList:
            self.adjacencyList[vertex] = []
        for edge in self.edgeList:
            self.adjacencyList[edge[0]].append(edge[1])
        return self.adjacencyList
 
def dijkstra(gp, start):
    completedNode = []
    shortestPath = {}
    adjacencyList = gp.make_adjacencyList()
    for vertex in gp.vertexList: shortestPath[vertex] = (None, None)
 
    shortestPath[start] = (start, 0)
    current = start
    vertexs = set(gp.vertexList)
    while vertexs:
        print(shortestPath)
        minVertex = current
 
        vertexs.remove(current)
        for adj_node in adjacencyList[minVertex]:
            if adj_node not in completedNode:
                n_weight = gp.weightList[(minVertex, adj_node)] + shortestPath[minVertex][1]
                shortestPathWeight = shortestPath[adj_node][1]
 
                if shortestPathWeight is None:
                    shortestPath[adj_node] = (minVertex, n_weight)
                else:
                    if shortestPathWeight > n_weight:
                        shortestPath[adj_node] = (minVertex, n_weight)
 
        for vertex in vertexs:
            if current is minVertex:
                if shortestPath[vertex][1] is not None:
                    current = vertex
            else:
                if shortestPath[vertex][1] is not None:
                    if shortestPath[vertex][1] < shortestPath[current][1]:
                        current = vertex
 
        completedNode.append(minVertex)
    return shortestPath
 
def shortest_path(gp, start, end):
    sh_matrix = dijkstra(gp, start)
    current = None
    shortestPath = []
    shortestPath.append(end)
    while current != start:
        current = sh_matrix[end][0]
        shortestPath.append(current)
        end = current
    shortestPath.reverse()
    print(shortestPath)
    # return shortestPath
 
vertexList = ['A', 'B', 'C', 'D', 'E', 'F']
gp = graph()
 
for vertex in vertexList:
    gp.addVertex(vertex)
gp.addEdge('A', 'B', 4)
gp.addEdge('A', 'F', 3)
gp.addEdge('B', 'E', 10)
gp.addEdge('B', 'C', 5)
gp.addEdge('C', 'F', 1)
gp.addEdge('D', 'E', 3)
gp.addEdge('E', 'F', 8)
# print(gp.weightList)
 
shortest_path(gp, 'A', 'D')
shortest_path(gp, 'A', 'F')
shortest_path(gp, 'B', 'F')
 
 

수도코드를 보고 좀 더 고민해봐야할듯, O(N^2)