그래프 관련 알고리즘 - 다익스트라, 플로이드-워셜, 크루스칼 - 2021/05/06

1. 다익스트라 알고리즘

 

다익스트라 알고리즘은 가장 기본적인 최단경로 알고리즘이다. 값들을 비교하면서 최단경로를 갱신한다. 시간복잡도는 O(N^2)이다.

 

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

 

2. 플로이드- 워셜 알고리즘

 

플로이드-워셜 알골리즘은 최단경로를 찾을 때, 값의 범위가 크지 않을 때, 유용하게 사용할 수 있다. 직접가는 경로와 경유해서 가는 경로 중 최솟값을 경로에 저장한다. 시간복잡도는 O(N^3)이다.

 

n=int(input())
m=int(input())

INF=int(1e9)
graph=[[INF]*(n+1) for i in range(n+1)]
for i in range(n+1):
    graph[i][i]=0
    
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a][b]=c

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

 

3. 크루스칼 알고리즘

 

크루스칼 알고리즘은 가장 대표적인 최소신장트리로 find_parent 함수와 union_parent 함수를 이용해서 구현할 수 있다. 간선을 하나씩 확인하면서 현재의 간선이 싸이클을 발생시키는지 확인한다. 싸이클을 발생하지 않으면 신장트리에 추가하고 발생시키면 추가하지 않는다. 시간복잡도는 O(NlogN)이다.

 

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]
        
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
        
v,e=map(int,input().split())
parent=[i for i in range(v+1)]
edges=[]
result=0
    
for i in range(e):
    a,b,c=map(int,input().split())
    edges.append((c,a,b))

edges.sort()
for i in edges:
    cost,a,b=i
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost