최단 경로 탐색 알고리즘

Yerim·2021년 8월 25일
0

Algorithm

목록 보기
1/1

최단 경로 탐색 알고리즘이란?

그래프의 한 노드에서 다른 노드까지의 경로 중 간선의 가중치의 합이 최소가 되는 경로를 찾는 알고리즘

  • Single Source : 하나의 시작점에서 다른 모든 점까지의 최단 경로를 구하는 알고리즘
  • Single Destination : 하나의 목적지까지 다른 모든 점에서 출발하는 최단 경로를 구하는 알고리즘
  • Single Pair : 하나의 시작점에서 다른 하나의 목적지까지의 최단 경로를 구하는 알고리즘
  • All Pair : 그래프의 모든 쌍에 대하여 최단 경로를 탐색하는 알고리즘

💡 BFS

그래프의 모든 간선의 가중치가 같거나, 가중치가 없을 경우

  • Queue를 이용하여 구현할 수 있다.
  • 경로 탐색의 시작점을 Queue에 push한다.
  • Queue가 empty 상태가 될 때까지 무한루프
  • Queue의 front를 꺼낸 후 해당 노드와 인접한 노드들이 아직 방문하지 않은 노드일 경우 Queue에 push

📍 구현 코드 예시

   while (!q.empty()) {
        int node = q.front();
        q.pop();   // front 노드 꺼내기
        visited[node] = 1;   // 방문
        for (int i = 0; i < EDGE[node].size(); i++) {
            int neigh = EDGE[node][i];   // 인접 노드
            if (visited[neigh] == -1) {
                q.push(neigh);
                dis[neigh] = dis[node] + 1;
                visited[neigh] = 1;
                /* 방문하지 않은 노드일 경우 Queue에
                push 후 방문 표시, 
                distance(거친 노드 수) update */
            }
        }
    }

💡 Dijkstra

음의 가중치가 없는 그래프에서 Single Source, Single Destination, Single Pair 경로 탐색 가능

  • 출발점에서 인접한 노드들에 대한 가중치 update
  • 그 중 가장 짧은 경로를 가진 노드를 최단 경로에 추가(방문)
  • 아직 방문하지 않은(최단 경로에 포함하지 않은) 노드들에 대하여 다시 가중치 update
    가중치 = min(update된 최단 경로에서의 가중치, 원래 가중치)
  • 모든 노드를 방문하여 최단 경로에 추가할 때까지 위의 2, 3번 과정 반복

📍 구현 코드 예시

Dijkstra(const int n, const int v) {
	// n은 노드의 수, v는 시작점
    for(int i=0; i<n; i++) {   // initialize
    	s[i] = false;   // 방문 여부
        dist[i] = length[v][i];   // 시작 점에서의 거리
    }
    s[v] = true;   // 시작점 방문
    dist[v] = 0;   // 시작점의 거리는 0
    for(int i=0; i<n-2; i++) {   // 시작점에서 n-1개의 path를 거쳐 목적지로 도달
    	int u = Choose(n);   // 최단 경로를 가지는 노드 선택
        s[u] = true;   // 방문
        for(int w=0; w<n; w++)
        	if(s[w] == false)
            	dist[w] = min(dist[u] + length[u][w], dist[w]);
                // update된 최단 경로를 가지고 다른 노드까지의 최단 경로 update
     }
  • Complexity
    • 최단 경로에 포함될 다음 노드를 선택할 때 : O(nn)
    • 인접 List 또는 인접 행렬를 사용할 경우 한 경로가 update될 때마다 다른 각 노드에 대한 최단 경로가 update되어야 한다.
    • Total : O(n2n^2)
    • (추후 수정)

💡 Bellman-Ford

음의 가중치를 포함하는 그래프에서 Single Source, Single Destination, Single Pair 경로 탐색 가능

  • Dijkstra에서 음의 가중치가 있을 경우 cycle이 형성되어 무한반복 ➡ 최단 경로를 구할 수 없음
  • n개의 점이 있는 그래프에서 한 점에서 다른 한 점까지의 최단 경로는 사이클이 없을 때 최대 n-1개의 간선을 지난다.
  • 한 점 d에서 다른 점 v까지 이동한다고 할 때, 시작점에서 v까지 k개의 간선을 거친다고 가정하면, 시작점에서 d까지는 k-1개의 간선을 거친다.
  • 시작점에서 d까지의 경로는 현재까지 구한 최단 경로이므로 여기에 d에서 v까지의 최단경로를 더하면 새로운 최단경로가 된다는 것을 보장한다.
    D(v, k) = min{ D(v, k-1), min(D(d, k-1) + length(d, v)) }
  • D(v, k)는 k개의 간선을 거쳐 v까지 도달하는 최단 경로를 말한다.
  • 여기서 dv에 인접한 모든 점들을 말한다.
  • 이 과정을 최단 경로에 n-1개의 간선이 포함될 때까지 반복한다.
  • n-1개의 간선을 가지는 최단 경로를 구한 후, 다시 한번 최단 경로 update를 수행할 때 이전 경로와 다른 최단경로가 update될 경우, 음의 가중치가 있음을 알아낼 수 있다.
  • 이 경우 사이클이 발생하기 때문에 정상적인 최단경로를 계산할 수 없다.

📍 구현 코드 예시

BellmanFord(const int n, const int s) {
	// n은 노드의 수, s는 시작점
    for(int i=0; i<n; i++) dist[i] = length[s][i] // 시작점에서의 경로 초기화
    for(int k=2; k<n-1; k++)   // n-1개의 경로
    	for(each v such that v != s and v has at least one incoming edge)   // 시작점 외에 다른 점들까지
            	for(each <w, v> in the graph)
                	dist[v] = min(dist[v], dist[w] + length[w][v])   // 최단경로 update
}
  • Complexity
    • 인접 행렬을 사용할 경우 O(n3n^3)
    • 인접 리스트를 사용할 경우 O(nene)
profile
Backend-Developer

0개의 댓글