rom collections import deque

def dijkstraAlgorithms(graph: dict, startPoint: int, endPoint: int): # find minimum distance from startPoint to endPoint in graph.
    # graph is given in form of Dictionary like {(1, 2): 1, (2, 3): 1, (3, 4): 2, (2, 4): 5, (1, 4): 7}.
    # startPoint and endPoitn is given in form of Integer.

    # 1. get all vertices connected with startPoint.
    def findVertices(graph: dict, targetPoint: int):
        verticesDict = dict({})
        for edge in graph:
            tmp = [point for point in edge if point != targetPoint]
            if len(tmp) == 1:
                verticesDict[(tmp[0])] = edge
        return verticesDict
    
    # 2. find all vertices of graph.
    def findAllVertices(graph: dict):
        verticesSet = set({})
        for edge in graph:
            for point in edge:
                verticesSet.add(point)
        return verticesSet
    unfoundVertex = findAllVertices(graph)

    verticesDict = {startPoint: 0} # save each vertices and its distance from startPoint as key and value.
    currentVertex = startPoint
    connect = deque([])
    # 3. iterate all edges until all is found.
    i = 0
    while unfoundVertex:
        i += 1
        currentlyConnectedVertices = findVertices(graph, currentVertex)
        for vertex, edge in currentlyConnectedVertices.items():
            if vertex in unfoundVertex:
                connect.append(vertex)
            if vertex in verticesDict:
                verticesDict[vertex] = min(verticesDict[vertex], verticesDict[currentVertex] + graph[edge])
            else:
                verticesDict[vertex] = verticesDict[currentVertex] + graph[edge]
        while True:
            currentVertex = connect.popleft()
            if currentVertex in unfoundVertex:
                break
        unfoundVertex.remove(currentVertex)

    return verticesDict[endPoint]

어딜 내놔도 부끄러운, 무지성으로 짜본 다익스트라 알고리즘...

주의 효율성과 가독성은 처참합니다.
다익스트라 처음 공부하면서 짜본 알고리즘이고, 우선순위큐를 적용하지 않아 효율성이 개똥!@#$만큼 나온다고 보시면 되겠습니다.

dijkstraAlgorithms()의 매개변수로 graph: dict, start: int, end: int를 받는데,
graph의 key값은 node와 node 사이의 간선을 뜻하고, value값은 가중치(weight)를 의미합니다.
만약 (1, 2): 3 같은 경우, 1번 노드와 2번 노드에 간선이 있는데 해당 간선의 가중치는 3이란 의미로 받아들여주시면 되겠습니다.

start는 시작 위치의 Node 번호, end는 목적 지점의 Node 번호를 뜻합니다.

#1., #2. 우선 그래프에 있는 모든 노드와 그의 인접노드를 추출합니다. 사실 저렇게 이상하게 짤 필요는 없고,

verticesDict = dict({})
for edge in graph:
	node1, node2 = edge
    if node1 not in verticesDict:
    	verticesDict[node1] = []
    if node2 not in verticesDict:
    	verticesDict[node2] = []
    
    verticesDict[node1].append(node2)
    verticesDict[node2].append(node1)

위와 같이 짜는 게 훨씬 파이써닉할 것입니다.

이후 verticesDict를 선언하고 여기에 각 노드까지의 거리를 저장할 것입니다. 왜 list가 아니라 dict를 썼느냐? 는 중요하지 않습니다. 그냥 저장하기만 하면 다 되는 것 아닐까요? ㅎㅎㅎ...은 사실 dict가 list보다 탐색효율이 좋다고 알고있기 때문에 한번 써봤습니다.
사실 대부분 코딩테스트에 나오는 다익스트라의 경우에는 굳이 dict 안 써도 될 거 같네요.

사족이 길었습니다.

본격적으로 다시 코드해설 들어가보겠습니다.
connect란 deque을 선언하여 여기에 각 인접노드를 탐색할 때, 해당 노드의 인접노드를 전부 담을 것입니다.
이 때, 인접노드를 담을 땐 appendleft() 메소드를, 인접노드를 빼서 탐색할 땐 pop() 메소드를 사용합니다. 왜 append()가 아니라 ppendleft()를 쓰느냐? 방금 지나왔던 곳을 바로 되돌아가거나 한쪽 노드만 집중탐색하는 것을 방지하기 위함입니다. 일단은 코드효율성을 위해 덱을 썼는데, append()를 하고 바로 pop()을 하는 건 이상하잖아요.

하여튼 그래서, start부터 시작해서 인접노드를 탐색 후 currentlyConnectedNode(현재 연결된 모든 노드)에 현재 노드의 인접노드를 모두 담아줍니다.
이후 이 안의 각 노드/간선을 탐색할 건데, 만약 해당 노드가 아직 탐색되지 않은 노드라면 connect에 다음 탐색할 노드로 저장해줍니다.

그리고 이 인접노드까지 가는 최단거리를 계산하여 verticesDict에서 갱신해줍니다.

그리고 다음 탐색할 노드를 connect에서 pop()하여 갱신해줍니다.
근데 connect에는 마음대로 어떤 노드의 인접노드를 무지성으로 appendleft()했기 때문에, 이미 방문한 노드, 방문 안 한 노드가 죄다 섞여있습니다. 그러니까, 만약 connect.pop()한 노드가 이미 방문한 노드라면 날려버리고, 방문하지 않은 노드가 등장할 때까지 pop()을 진행해줍니다.

이후, 방문하지 않은 노드를 unfoundVertices에서 제거해주고, 해당 노드를 현재 노드로 갱신합니다.

이걸 connect가 빌 때까지 반복하면 됩니다.