개발공부일지

플로이드-워셜(Floyd-Warshall)모든 노드 간의최단 경로를 구하는알고리즘음의 간선이 포함되어 있어도 사용 가능음수 사이클이 있으면 정상 동작하지 않음알고리즘 복잡도: O(V^3)  플로이드-워셜 알고리즘 Flow (1 / 8)노드 수 V일 때, V x V만큼의 메모리 필요모든 노드에서 모든 노드로 가는 경로 DP 방식 업데이트자기 자신 노드에서 출발은 0으로 업데이트  플로이드-워셜 알고리즘 Flow (2 / 8)각 노드에서 인접 노드로 가는 경로 DP 방식 업데이트  플로이드-워셜 알고리즘 Flow (3 / 8)2번을 지나 2번의 인접노드로 가는 경로들 업데이트6이 2를 거쳐서 다른 노드로 가는 경로 업데이트  플로이드-워셜 알고리즘 Flow (4 / 8)3번을 지나 3번의 인접노드로 가는 경..

벨만-포드(Bellman-Ford)음수 간선이 포함되어 있어도 최단 경로 구할 수 있음 (↔ 다익스트라는 음수 간선 포함 X)다만, 음수 사이클이 있으면 정상 동작하지 않음매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림알고리즘 복잡도: O(VE)  ** V: 노드 // E: 간선 **   음수 간선이 포함된 가중그래프노드1 -> 노드4 최단 경로다익스트라 적용 시: 7 최단 경로: 5   벨만-포드 알고리즘 Flow (1 / 2)다음과 같이 노드와 간선 가중치 정보가 있을 때, A 노드에서 다른 노드들에 대한 최단 거리 구하기1번 노드부터 돌면서 모든 간선들에 대한 정보를 갱신해 줌(더 작은 값이면 업데이트)   벨만-포드 알고리즘 Flow (2 / 2)다음과 같이 노드와 간선 가중치 정보가 있..

최단 경로 알고리즘가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용최단 경로 알고리즘 다익스트라벨만-포드플로이드-워셜  다익스트라(Dijkstra)출발점에서 목표점까지의 최단 경로를 구하는 알고리즘한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음간선에 음의 가중치가 없어야 함그리디 + DP(Dynamic Programming)형태알고리즘 복잡도: O(ElogV)  ** E: 간선 수 / V: 노드 수 **  다익스트라 알고리즘 Flow다음과 같이 노드와 간선 가중치 정보가 있을 때,A 노드에서 다른 노드들에 대한 최단 경로 구하기A 노드부터 A와 연결된 간선 경로 업데이트연결된 간선 중 가장 최단 경로 선택: B (..