[알고리즘] 다익스트라

그래프 - 시작점에서 각 노드간 최단거리를 구하는 알고리즘

원리 :

1. 시작점을 기준으로 인접 노드 거리 갱신

2. 갱신한 노드에서 거리가 짧은 순으로 방문하여 그 노드의 인접 노드 갱신 및, 시작점과의 거리 비교 후 갱신

3. 더 이상 방문하지 않은 노드가 없을 때까지 반복

import math
def solution(n, edge):
    answer = 0
 
    graph = [[] for _ in range(n+1)]
    for a, b in edge: # a - b
        graph[a].append(b)
        graph[b].append(a)
    distance = [math.inf] * (n + 1) # 시작점에서 각 노드의 거리
    isvisit = [False] * (n + 1) # 이미 방문한 노드 체크
    isvisit[1] = True # 시작점은 방문한 것으로 체크
    distance[1] = 0 # 시작점의 거리 0으로 체크
    def get_smallest_node() :
        min_value = math.inf
        idx = 0
        for i in range(1, n+1):
            if distance[i] < min_value and not isvisit[i]:
                min_value = distance[i]
                idx = i
        return idx
    def dijkstra(start):
        distance[start] = 0
        isvisit[start] = True
        for j in graph[start]:
            distance[j[0]] = j[1]
 
        for i in range(n-1) :
            now = get_smallest_node()
            isvisit[now] = True
            for j in graph[now]:
                comp_dis = distance[now] + j[1]
                if comp_dis < distance[j[0]]:
                    distance[j[0]] = comp_dis
 
    dijkstra(1)
    distance.remove(math.inf)
    print(distance)
    for dis in distance:
        if dis == max(distance):
            answer += 1
    return answer