Summary

• Floyd Warshall

Description

'모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면, 플로이드 와샬 알고리즘을 사용해야 한다. Dynamic Programming 기법으로 구현할 수 있다. Vertex를 N이라 한다면, 행렬의 크기는 N X N 으로 구현되어 있어야 하고 각 정점에서 다른 정점으로의 거리를 표현해야 한다. 자기 자신의 거리는 0으로 둬야 하며, 자신으로 부터 Edge가 연결되어 있지 않은 Vertex는 거리는 무한대로 표현해 놓아야 한다. 그리고 나서, 삼중 포문을 통해서 경유지를 N까지 증가시켜가며 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구할 수 있다.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j]
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

Data Structure

• Array (2차원)

Time Complexity

• O(n^3) (n : Vertex의 갯수)

Code

• 2021 카카오 블라인드 코딩테스트 (합승 택시 요금)

https://programmers.co.kr/learn/courses/30/lessons/72413

#include <iostream>
#include <string>
#include <vector>

std::vector<std::vector<int> > make_floyd(size_t n, std::vector<std::vector<int> >graph)
{
	for (size_t k = 0 ; k < n ; k++)
		for (size_t i = 0 ; i < n ; i++)
			for (size_t j = 0 ; j < n ; j++)
				if (graph[i][k] + graph[k][j] < graph[i][j])
					graph[i][j] = graph[i][k] + graph[k][j];
	return (graph);
}

std::vector<std::vector<int> > make_graph(size_t n, std::vector<std::vector<int> >fares)
{
	std::vector<std::vector<int> >graph;
	graph.resize(n, std::vector<int>(n, 999999));

	for (size_t i = 0 ; i < fares.size(); i++)
	{
		graph[fares[i][0] - 1][fares[i][1] - 1] = fares[i][2];
		graph[fares[i][1] - 1][fares[i][0] - 1] = fares[i][2];
	}
	for (size_t i = 0 ; i < n ; i++)
		graph[i][i] = 0;
	return (graph);
}

int solution(int n, int s, int a, int b, std::vector<std::vector<int> >fares)
{
    int answer = 99999999;
    size_t _n = static_cast<size_t>(n);
    a--;
    b--;
    s--;

    std::vector<std::vector<int> > graph = make_graph(_n, fares);
    std::vector<std::vector<int> > floyd = make_floyd(_n, graph);

    for (size_t k = 0 ; k < _n ; k++)
	    answer = std::min(answer, floyd[s][k] + floyd[k][a] + floyd[k][b]);
    return (answer);
}