그래프에서 음의 사이클 구하기벨만 포드 알고리즘을 이용하는 것과 플로이드 워셜 알고리즘을 이용하면 그래프에서 음의 사이클을 찾아낼 수 있다. 플로이드 워셜 알고리즘을 이용한 방법mp를 그래프라고 할 때, 플로이드 워셜 알고리즘에서 사이클의 존재 여부는 mp[i][i] 값을 통해서 확인할 수 있다. 플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하기 위해 각 정점 i에서 j로 가는 최단 경로를 mp[i][j]에 저장하게 된다.사이클이 없는 경우라면, 어떤 정점에서든 자신으로 돌아오는 경로가 존재하지 않으므로 mp[i][i]는 초기화된 값인 INF를 유지하게 된다.반면, 사이클이 존재하는 경우 해당 경로의 길이를 갱신하게 되어 mp[i][i] (자기 자신에게로 돌아오는 경로)가 INF가 아닌 값..
최단경로
코드 # 노드의 개수가 20000개이므로 시간복잡도가 O(N^3)인 플로이드-워셜은 효율이 낮다. # 가중치는 10 이하의 자연수이므로 다익스트라를 사용할 수 있다. # O(Elogv)로 해결 가능 import sys, heapq # 우선순위 큐를 이용한 다익스트라를 구현할 것이므로 heapq모듈 사용 INF = 987654321 input = sys.stdin.readline n,m = map(int, input().split()) k = int(input()) graph = [[] for _ in range(n+1)] # 입력하기 쉽게 (n+1)로 해주었음 visited = [INF]*(n+1) # 방문 경로 for _ in range(m): x,y,z = map(int, input().split()..
최단경로 알고리즘 BFS 시작점으로부터 거리가 가까운 정점부터 탐색 가중치가 없는 그래프의 최단 경로를 찾는 데 쓰일 수 있다. 간선의 가중치가 있는 그래프의 최단 경로는 어떻게 찾을까 - Dijkstra 알고리즘 - Bellman-Ford 알고리즘 - SPFA 알고리즘 - Floyd 알고리즘 경로의 길이: 경로가 지나는 간선의 가중치의 합 v1에서 v2로 가는 되단 경로: v1에서 v2로 가는, 경로의 길이가 최소인 경로 너비 우선 탐색(BFS) 1. 시작점을 큐에 넣는다 2. 큐에서 정점 하나를 뺀다. 3. 이 정점에 연결된 모든 정점들을 큐에 넣는다. (단, 큐에 이미 들어갔던 정점은 제외) dist[i] = dist[x] + 1 4. 큐에 원소가 남아 있다면 2번으로 돌아간다. Dijkstra 알..
