JUINTINATION

SSSP(Single-source shortest paths) 알고리즘이란?어떤 그래프에서 시작 노드부터 도착 노드까지의 최단거리를 구하는 알고리즘이다.SSSP 알고리즘은 대표적으로 3가지로 나눌 수 있다.그래프에 음의 간선이 없는 경우Dijkstra’s algorithm: O(|E| + |V| log |V|)음의 사이클이 존재하지 않는 경우Bellman-Ford algorithm: O(|V||E|)DAG(Directed Acyclic Graph, 유향 비순환 그래프)의 경우One pass of Bellman-Ford: O(|V||E|)DAG Shortest Path using Topological Sort: O(|V| + |E|)다익스트라 알고리즘(Dijkstra's Algorithm)dijkstra(..

위상정렬(Topological Sort)이란? 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 다음 라면 끓이기 예제를 보자 우리는 라면을 끓일 때 냄비에 물을 먼저 부어도 되고 라면 봉지를 먼저 뜯어도 되지만 계란은 맨 마지막에 풀어야 한다. 이러한 방향은 있지만 사이클은 없는 그래프를 간선의 방향을 거스르지 않고 한 줄로 정렬시키는 것이 위상정렬이라고 보면 될 것 같다. 위상정렬 알고리즘(1) 진입 간선이 없는 정점을 연결리스트 R의 맨 뒤에 연결하고 해당 정점과 그 정점의 진출 간선을 제거하는 과정을 반복한다. 의사 코드는 다음과 같으며 위의 예시를 구하는 과정은 그 다음 그림과 같다. topological_so..