[Algorithm] Floyd-Warshall (Swift)

안녕하세요 :)

오늘은 플로이드 와샬 알고리즘에 대한 포스팅입니다.

플로이드 와샬 (Floyd-Warshall) 알고리즘은 다이나믹 프로그래밍을 기초로 하고있는데요.

이 방법의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는 것 입니다.

예시로 좌측의 그래프의 정점 간의 이동 비용을 아래와 같은 2차원 배열로 나타낼 수 있습니다.

위 테이블은 정점 간 직접 연결되어, 한번 이동했을때의 비용을 나타낸 것인데요.
(직접적으로 연결이 안된 부분은 한번에 갈 수 없으니 무한으로 표기하였습니다.)

플로이드 마샬 알고리즘에서는 이러한 테이블을 시작점으로,
각 정점을 거쳤을 때의 비용과 vs 현재까지 계산된 최소비용 을 비교하여,
반복적으로 테이블을 갱신합니다.

  1. 우선 노드 1을 거쳐가는 경우를 생각해봅시다.

여기서 녹색으로 칠해져 있는 부분이 갱신될 부분입니다.

2에서 4까지, 노드 1을 거쳐서 가는 경우는 아래와 같이 계산할 수 있습니다.

[2에서1 비용: 1] + [1에서4 비용: 2] 을 합친 값 3 과 현재의 최소값 무한을 비교하여, 더 작은 값인 3으로 테이블을 갱신하게됩니다.

위의 한 과정을 매 노드마다 반복하게 되는데, Swift로 표현하면 아래와 같습니다.

감사합니다.

코로나 조심하세요

--

--

iOS Developer 🇰🇷🇬🇧

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store