이즈미르의 프로그래밍

이번에 알아볼 그래프 알고리즘은 최단 경로 알고리즘(Shortest path algorithms)이다. 최소 신장 트리(Minimum spanning tree)는 모든 노드를 최소한의 비용을 들여 연결한 그래프의 모습이라고 했다. 이와 다르게 그래프의 최단 경로 알고리즘은 한 노드에서 다른 노드로 이동할 때 거치는 간선들의 비용의 총합을 최소한으로 하는 경로를 구한다. 대표적으로 다익스트라(Dijkstra) 알고리즘과 플로이드(Floyd) 알고리즘이 있다. 각 알고리즘을 알아보기에 앞서 그래프와 최단 경로를 어떤 자료구조를 사용할 것인지 정의하자. 그래프를 나타낼 자료구조는 최소 신장 트리에서 소개한 것(weights 변수) 그대로 사용한다. https://izmirprogramming.tistory.c..