코생코사

https://m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort)  위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 ...blog.naver.com 위상 정렬이란순서가 정해져 있는 작업들을 선행 조건에 만족하도록 정렬하는 알고리즘정점 u에서 v로 가는 간선이 있을 때 항상 u 다음에 v가 나와야 하는 경우같이 순서가 정해져 있을 때 사용할 수 있다 위상 정렬을 쓸 수 있는 경우-> 그래프가 DAG(방향 비순환 그래프)인 경우 순환이 존재하는 그래프에서는 사용할 수 없다 +그래프의 종류https://6mini.github.io/computer%20science/2021/12/02/graph/ [..

https://www.youtube.com/watch?v=Ppimbaxm8d8&list=LL&index=36 벨만 포드 음의 간선이 있는 경우음수 간선 순환이 생기는 지도 알 수 있다시간 복잡도 O(VE)(다익스트라는 O(ElogV)) 벨만 포드 알고리즘1. 출발 노드 설정2. 최단 거리 테이블 무한으로 초기화3. 전체 간선을 돌면서 최단 거리 테이블 갱신3번을 노드 -1 만큼 반복 음수 간선 순환이 발생하는 지 확인하는 방법3을 한 번 더 반복해서 최단 거리 테이블이 또 갱신되면 음수 간선 순환이 발생(즉 3을 노드만큼 반복하면 된다) n: 노드 수m: 간선 수distance: 최단 거리 테이블edges: 간선 정보 벨만 포드 함수def bf(start, distance): distance[sta..