알고리즘 - 7) 다익스트라

1. 다익스트라 알고리즘(한 지점에서 시작해서 모든 노드로의 최단거리 구하기) - 양방향

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())

graph= []
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append((b,1))
    graph[b].append((a, 1))

distance = [INF]*(n+1)


def dijkstra(start){
    start = 0
    distance[start] = 0
    q = []
    heapq.heappush(q, (distance[start], start))
    
    while q:
        dist, x = heapq.heappop(q)
        if distance[x] < dist:
            continue
        for i in graph[x]:
            cost = dist+ i[1]
            if cost< distance[i[0]]:
                distance[i[0]] =cost
                heapq.heappush(q, (cost, i[0]))
}

2. 플로이드 워셜 (모든지점에서 모든지점으로 이동)

for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(n):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[b][k])

 

 

3. 서로소 집합( union, find) - 연결 여부에 따라서 표현

def union_parent(parent, a, b){
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else :
        parent[a] = b

}

def find_parent(parent, x){
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
}

 

4. 최소 신장 트리 (크루스칼 알고리즘) - 임의의 두 점 양방향일때 모두 연결(최소신장트리 의심)= 연결그래프

def union_parent(parent, a, b){
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else :
        parent[a] = b

}

def find_parent(parent, x){
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
}

n, m = map(int, input().split())
parent = [0]*(n+1)

edges = []
result = 0

for i in range(1, n+1):
    parent[i] = i

for _ in range(m):
    x, y, z = map(int, input().split())
    edges.append((z, x, y))

edges.sort()
total = 0

for edge in edges:
    cost, a, b = edge
    total += cost
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result+= cost

print(total - result)

 

 

5. 위상 정렬(순서가 존재하는 경우에 정렬)