학습 일자 : 2023.05.02

최단경로

DFS, BFS는 단순 연결성만 가지고 있는 그래프일 때 구현하는 방법

가중치가 있을 때는 결과가 완전히 달라짐. 가중치 있는 경우 구현하는 알고리즘이 바로 최단 거리임

다익스트라 알고리즘 (Dijkstra Algorithm) *

• 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구함
• 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 후,
• 해당 노드를 거쳐 다른 노드로 가는 비용 계산

탐욕적 알고리즘

최대 유량 문제

FloydWarshall

처음부터 끝까지 냅다 다해보는 것 → 동적 계획 법

겁나 비효율적이라서 잘은 안씀

결과는 동일함

실습