이번에는 최단 경로의 마지막 알고리즘인 플로이드 워셜 알고리즘에 대해서 살펴보자. 플로이드 워셜 알고리즘 플로이드 워셜의 특징이제까지 다익스트라와 벨만포드 알고리즘을 이용한 최단 경로를 구해봤다. 한 점에서 모든 점까지의 최단 거리를 구할 수 있었고 여차하면 음의 간선까지 처리할 수 있었는데 또 필요한 최단 거리 알고리즘이 있을까?있으니까 여기서 글을 쓰고 있다. ㅎ이번에 알아볼 알고리즘은 플로이드 워셜 알고리즘이다. 플로이드는 이전까지의 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단거리를 구하기 위한 알고리즘이다.물론 다익스트라, 벨만포드의 모든 정점을 출발점으로 해서 N번 돌리면 모든 정점에서의 최단거리를 구할 수 있다. 하지만 플로이드 워셜은 대체로 다익스트라, 벨만포드를 N번 돌릴 때보다 빠..

이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다.벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최단 거..

이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.! 다익스트라 알고리즘이란?다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결국 각 정점까지의 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다.다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다.S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시..

이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자.만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장 짧..