[알고리즘] 최단 경로 역추적

다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다.

최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역추적 접근 방법이 약간 다르다.

 

공통점

최단 거리가 업데이트 될 때 경로 역시 업데이트 한다.

 

다익스트라

path[NODE] = PREV

NODE에 도착하기 전 거쳐야 하는 노드가 PREV

 

경로 초기화

for (int i = 1; i <= n; i++)
{
   ...
   path[i] = i; // i 전에 들르는 노드는 i
}

 

경로 업데이트

 if (dist[a.second] > dist[curNode] + a.first)
{
    ...
    path[a.second] = curNode;
}

 

경로를 추적할 땐 dst -> src까지 거꾸로 내려간다.

vector<int> answer;
int x = dst;
while (x != path[x])
{
  answer.push_back(x);
  x = path[x];
}
answer.push_back(x);

//anwer 뒤집기
for (int i = sze - 1; i > -1; i--)
{
  printf("%d ", answer[i]);
}

//reverse 사용 #include <algorithm>
reverse(answer.begin(), answer.end());

 

플로이드와샬

플로이드 와샬에서 역추적은 재귀함수를 사용해서 top-down으로 접근한다.

마찬가지로 최단 거리가 업데이트 될 때 경로를 업데이트한다.

 

path[i][j] = k

i-> j로 갈 때 k를 거친다

 

경로 초기화

//경로 초기화
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      ...
      path[i][j] = i;
    }
  }

 

 

경로 업데이트 

  for (int k = 1; k <= n; k++)
  {
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        if (arr[i][j] > arr[i][k] + arr[k][j])
        {
          ...
          path[i][j] = k;
        }
      }
    }
  }

 

 

경로 역추적

vector<int> tmp;
void findPath(int from, int to)
{
  int prev = path[from][to];
  if (from == prev)
  {
    tmp.push_back(from);
    return;
  }

  findPath(from, prev);
  findPath(prev, to);
}

 

경로 출력

tmp.clear();
findPath(i, j);
tmp.push_back(j);

for (auto a: tmp)
{
   printf("%d ", a);
}