Algorithm/Theory3 [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘) Floyd-Warshall 알고리즘은 기존에 포스팅했던 Dijkstra 알고리즘이나 Bellman-Ford 알고리즘과 다르게, 모든 정점들 사이의 최단거리를 계산하는 알고리즘이다. 그래프의 초기 상태는 다음과 같다. 두 정점사이의 거리를 나타내는 dist 배열을 나타내보자. dist[i][j]는 정점 i에서 정점 j까지의 거리이다. dist 배열의 초기값은 i==j일때는 0으로, 정점 i와 정점 j가 연결되어있다면 두 정점을 잇는 간선의 가중치로, 두 정점이 연결되어있지 않다면 적당히 큰 수인 INF로 설정했다. 초기 dist배열의 모습은 아래와 같다. Floyd-Warshall 알고리즘의 핵심은 정점 k(14) dist[5][4]=min(dist[5][4],dist[5][2]+dist[2][4])=mi.. 2021. 8. 9. [Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘) Bellman-Ford 알고리즘은 Dijkstra 알고리즘과 마찬가지로 단일 정점에서 각 정점까지의 최단거리를 구하는 알고리즘이다. 시작점은 1번 정점이다. dist배열은 시작점으로부터의 거리를 나타내고 INF로 초기화 되어있다. 초기상태는 아래와 같으며 그래프의 구현은 인접 행렬(Adjacency Matrix) W로 되어있다. 시작점이 1번 정점이기 때문에 dist[1]을 0으로 갱신한다. 한 정점과 인접한 정점을 중심으로 갱신을 이어나간 Dijkstra 알고리즘과는 달리 Bellman-Ford 알고리즘은 매 수행마다 모든 간선(edge)에 대해 갱신을 진행한다. 한 간선이 정점 i에서 정점 j로 이어진다고 할 때, 다음 연산을 통해 갱신이 진행된다. dist[j]=min(dist[j],dist[i]+.. 2021. 4. 6. [Algorithm] Dijkstra Algorithm (다익스트라 알고리즘) Dijkstra 알고리즘은 단일 시작점에서 모든 정점으로의 거리를 구하는 알고리즘이다. 다음과 같은 그래프가 주어졌다고 하자. 해당 그래프는 인접 행렬(Adjacency Matrix) W로 구현되어 있다. 시작점은 1번이다. 위 그림에서 dist 배열은 시작점에 해당하는 1번 정점으로부터의 거리를 나타낸다. dist[i] : 1번 정점으로부터 i번 정점까지의 거리 dist 배열의 각 원소를 INF로 초기화 한다. 우선, 시작점에서 시작점으로의 거리를 0으로 설정한다. 그리고 시작점에 인접한 정점들의 거리를 갱신한다. 위 사진의 경우 1번 정점은 2번 정점과 3번 정점에 인접해있다. 정점까지의 거리는 각각 2와 3이다. Dijkstra 알고리즘의 핵심은 dist[j]를 구할 때, 특정 경유지(예를 들어 i.. 2021. 4. 6. 이전 1 다음
