Floyd-Warhsall Algorithm

프로그래머스 합승택시요금과 순위 문제에서 필요한 알고리즘이다.

합승택시요금 : Dijkstra algorithm or Floyd-Warshall algorithm
순위: Floyd-Warshall algorithm을 이용하는 전형적인 문제

문제는, Dijkstra와 Bellman-Ford 알고리즘을 알지만 Floyd-Warshall 알고리즘은 내가 모르고 있다는 것.

Dijkstra Algorithm

    fun dijkstra(distanceMatrix: List<MutableList<Int>>, start: Int, end: Int) {
       var shortestDistance: Int
       var shortestV = end
       var visited = MutableList(distanceMatrix.size) { 0 }
       visited[0] = 1
       visited[start] = 1
       while (visited.any { it == 0 }) {
           shortestDistance = Int.MAX_VALUE
           for (i in 1 until distanceMatrix.size) {
               if (visited[i] == 0) {
                   if (shortestDistance > distanceMatrix[start][i]) {
                       shortestDistance = distanceMatrix[start][i]
                       shortestV = i
                   }
               }
           }
           visited[shortestV] = 1
           // 이제 distanceMatrix 갱신.
           for (i in 1 until distanceMatrix.size) {
               for (j in 1 until distanceMatrix.size) {
                   if (distanceMatrix[i][j] > distanceMatrix[i][shortestV] + distanceMatrix[shortestV][j]) {
                       distanceMatrix[i][j] = distanceMatrix[i][shortestV] + distanceMatrix[shortestV][j]
                   }
               }
           }
       }
   }

Floyd-Warshall Algorithm

    fun floydWarshall(distanceMatrix: List<MutableList<Int>>) {
       var shortestDistance = Int.MAX_VALUE
       var shortestV = 1
       // mid -> start -> end 순으로 해야한다
       for (midNode in 1 until distanceMatrix.size) {
           for (startNode in 1 until distanceMatrix.size) {
               // going through midNode, calculate the shortest distance from start to end
               for (endNode in 1 until distanceMatrix.size) {
                   if (distanceMatrix[startNode][endNode] >
                       distanceMatrix[startNode][midNode] + distanceMatrix[midNode][endNode]
                   ) {
                       distanceMatrix[startNode][endNode] =
                           distanceMatrix[startNode][midNode] + distanceMatrix[midNode][endNode]
                   }
               }
           }
       }
   }

처음 Floyd-Warshall 알고리즘을 구현할 때 정확성 테스트에서 계속 몇개가 실패가 떴다.
진짜 2시간을 넘게 다른 사람의 코드와 비교해도 똑같았는데... 알고보니 3중 for loop를 돌릴 때, midNode -> startNode -> endNode 순으로 돌려야한다. (나는 startNode -> midNode -> endNode 순으로 했다가 틀렸다. 솔직히 이게 왜 틀린지는 잘 모르겠다..)