huhsae's day huhsae's day

벨만포드 알고리즘이 글은 GeeksforGeeks의 Bellman–Ford Algorithm | DP-23를 번역한 글입니다. 그래프와 그래프의 source 정점 src를 고려하여, src부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라와 차이점은 그래프의 간선이 음의 값을 가질 수 있다는 점이다. 최단 거리문제는 다익스트라를 활용하여 해결할 수 있다. 다익스트라 알고리즘은 그리디 알고리즘 이며 피보나치 힙을 사용한다면 O(VlogV)의 시간 복잡도를 가졌다. 하지만 다익스트라는 음의 값을 가진 그래프에서는 사용할 수 없으며, 벨만포드를 사용하여야 한다. 벨만포드는 다익스트라보다 간단하며 분산 시스템에 잘 맞다. 하지만 시간 복잡도는 O(VE)로 다익스트라보다 복잡하다.알고리즘Input : 그..

플루이드 와샬 알고리즘GeeksforGeeks의 Floyd Warshall Algorithm | DP-16를 번역한 글입니다.플루이드 와샬은 모든 쌍의 최단거리를 구하는 문제이다. 주어진 가중치가 있는 방향 간선에서 모든 정점 사이의 최단거리를 해결하는 문제이다. 첫번째로 그래프 메트릭스와 같은 솔루션 메트릭스를 초기화 한다. 그 다음 모든 정점을 중간 정점으로 고려하면서 솔루션 메트릭스를 갱신할 것이다. 이 알고리즘의 아이디어는 모든 정점을 하나하나 선택하여 모든 최단거리를 갱신하는 것인데, 선택된 정점을 중간 정점으로 포함하는 것이다. 정점 K를 중간 정점으로 선택한다면, 이미 {1,2,3, ... k-1}의 정점들은 중간 정점으로 구려된 후이다. 모든 정점의 쌍 (i, j)을 시작점과 끝점으로 여긴..

다익스트라 최단거리 알고리즘geeksforgeeks - Dijkstras shortest path algorithm 을 번역한 글입니다.그래프와 그래프 속에 시작점(source vertex)이 주어진다면, 그래프안에서 시작 정점으로부터 모든 정점까지의 가장 짧은 거리를 찾는 알고리즘 다익스트라의 알고리즘은 프림의 최단 신장트리 알고리즘과 닮았다. 프림의 최단 스패닝트리(Minimum spanning tree - MST)처럼, 주어진 시작점을 루투로 하여 최단 길이 트리(Shortest path tree-SPT)를 만들 것이다. 알고리즘의 모든 스탭에서 소스로부터 가장짧으면서 아직 포함되지 않은 set에 있는 정점을 찾을 것이다. 다음은 다익스트라 알고리즘에서 가장 짧은 길을 찾기위한 자세한 step이다...