플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) Node.js

 

플로이드 알고리즘이란?

플로이드 워셜 알고리즘은 그래프 상에서 가능한 모든 경로의 최단거리를 뽑아내는 문제입니다. 

플로이드 워셜 알고리즘의 시간복잡도는 O(V^3)입니다. 그래프 상에서 경로의 최단거리를 구해내는 다익스트라 알고리즘과는 다르게 음의 가중치도 사용할 수 있습니다. 

플로이드는 이 알고리즘을 개발하고 튜링상을 수상합니다.

 

 

 

플로이드 알고리즘 설명

플로이드 워셜 알고리즘을 적용하기에 가장 좋은 분야는 방향성 그래프가 주어지는 상황입니다. 예를 들어 vertex 4개가 다음과 같은 방향성을 가진 그래프가 있다고 가정합니다.

 

 

이 그래프에서 1에서 3으로 가기 위해서는 stopover가 있어야 합니다. 3에서 1로는 갈 수 있지만 1에서 3으로 가기 위해서는 1-2-3을 거쳐 가야 하고, 혹은 1-4-3을 거쳐 가야 합니다.

• 1-2-3을 거치는 경우 최단 거리는 6 + 10 = 16이 됩니다.
• 1-4-3을 거치는 경우 최단 거리는 9 + 4 = 13이 됩니다.

즉 1에서 3으로 가는 최단 거리는 13이 됩니다.

플로이드 워셜 알고리즘은 임의의 노드 SRC부터 DST까지 가는데 최단 거리가 직접 연결되어 있다면 가중치를 계산하고, 만약 경로가 존재하지 않으면 무한(INF)로 초기화 합니다. 

 

 

플로이드 워셜 알고리즘 구현은 반복문 3개를 사용합니다. 가장 먼저 오는 반복문은 중간 노드인 STOPOVER가 되고, 시작점, 도착지점 순서로 반복문을 구현합니다. 

 

Floyd Warshall Algorithm

 

 

 

Node.js 소스코드

 

 

 

// 방향성 그래프를 그리는 함수
function createGraphByMatrix(num, edges) {
    
    const matrix = [];
    
    const INF = 101;
    for (let i = 0; i <= num; i++) {
    
      matrix.push(Array(num + 1).fill(INF));
      matrix[i][i] = 0;
    }
    edges.forEach(([src, dst, weight]) => {
      matrix[src][dst] = weight;
    });
    return matrix;
  }
  
// 메인 함수  
  function FloydWarshall(num, edges) {
    const matrix = createGraphByMatrix(num, edges);

    const distance = createGraphByMatrix(num, edges);

	// 플로이드 워셜 알고리즘(반복문 3개 구현)
    // 가장 첫번째 반복문은 중간 노드지점
    for(let stopover=1; stopover<=num; stopover++){
    	// 두번째 반복문은 시작지점
        for(let src=1; src<=num; src++){
        	// 세번째 반복문은 도착지점
            for(let dst=1; dst<=num; dst++){
            	// 중간노드를 거쳐 오는 것과 다이렉트 경로를 비교
                if(distance[src][stopover] + distance[stopover][dst] < distance[src][dst]){
                    distance[src][dst] = distance[src][stopover] + distance[stopover][dst];
                }
            }
        }
    }


    const INF = 101;

	// 배열 중 무한으로 된 부분을 'null'로 변경
    const nulled = distance.map((row)=>{
        return row.map(col=>{
            if(col === INF) return null;
            else return col;
        })
    })

	// 초과된 행,열을 제거
    return nulled.slice(1).map(row=>row.slice(1));
  }

 

 

 

 

[Algorithm] 조합 최적화 알고리즘 subsetSum Node.js

 

[Algorithm] TSP 알고리즘(해밀턴 경로 방문 판매원 문제) Node.js

 

[Algorithm] 동적 프로그래밍 LIS 문제 (Memoization VS Tabulation)