다 익스트라의 알고리즘 질문 ​​아래의 코드에서

Question

:

#define MAX_VERTICES 260000 

#include <fstream> 
#include <vector> 
#include <queue> 
#define endl '\n' 
using namespace std; 

struct edge { 
    int dest; 
    int length; 
}; 

bool operator< (edge e1, edge e2) { 
    return e1.length > e2.length; 
} 

int C, P, P0, P1, P2; 
vector<edge> edges[MAX_VERTICES]; 
int best1[MAX_VERTICES]; 
int best2[MAX_VERTICES]; 

void dijkstra (int start, int* best) { 
    for (int i = 0; i < P; i++) best[i] = -1; 
    best[start] = 0; 
    priority_queue<edge> pq; 
    edge first = { start, 0 }; 
    pq.push(first); 
    while (!pq.empty()) { 
     edge next = pq.top(); 
     pq.pop(); 
     if (next.length != best[next.dest]) continue; 
     for (vector<edge>::iterator i = edges[next.dest].begin(); i != edges[next.dest].end(); i++) { 
      if (best[i->dest] == -1 || next.length + i->length < best[i->dest]) { 
       best[i->dest] = next.length + i->length; 
       edge e = { i->dest, next.length+i->length }; 
       pq.push(e); 
      } 
     } 
    } 
} 

int main() { 
    ifstream inp("apple.in"); 
    ofstream outp("apple.out"); 

    inp >> C >> P >> P0 >> P1 >> P2; 
    P0--, P1--, P2--; 
    for (int i = 0; i < C; i++) { 
     int a, b; 
     int l; 
     inp >> a >> b >> l; 
     a--, b--; 
     edge e = { b, l }; 
     edges[a].push_back(e); 
     e.dest = a; 
     edges[b].push_back(e); 
    } 

    dijkstra (P1, best1);   // find shortest distances from P1 to other nodes 
    dijkstra (P2, best2);   // find shortest distances from P2 to other nodes 

    int ans = best1[P0]+best1[P2]; // path: PB->...->PA1->...->PA2 
    if (best2[P0]+best2[P1] < ans) 
     ans = best2[P0]+best2[P1]; // path: PB->...->PA2->...->PA1 
    outp << ans << endl; 
    return 0; 
} 

이 무엇 : if (next.length != best[next.dest]) continue;이 사용? 루프를 통해 우리가 이미 가지고있는 것과 동일한 대답을 줄 수있는 상황을 피하기 위해서입니까?

감사합니다!

Answer 1

이 줄은 C++의 priority_queue에 reduce_key 함수가 없다는 사실을 처리하는 방법입니다.

즉, pq.push(e)을 수행 할 때 이미 힙에 같은 대상이있는 엣지가 있으면 힙에 이미있는 가장자리의 키를 줄이는 것이 좋습니다. 이것은 C++의 priority_queue로는 쉽게 수행 할 수 없으므로 핸들하는 간단한 방법은 동일한 대상에 해당하는 힙에서 여러 엣지를 허용하고 힙에서 팝하는 첫 번째 (각 dest에 대해)를 제외한 모든 엣지를 무시하는 것입니다.

이렇게하면 복잡도가 O(ElogV)에서 O(ElogE)으로 변경됩니다.

Answer 2

우선 priority_queue가 동일한 에지를 2 번 포함하지만 각각 다른 "길이"를 갖는 경우를 생각해보십시오.

길이가 Y 인 모서리 X를 누른 다음 다시 모서리 X를 밀면이 문제가 발생할 수 있지만 이번에는 길이가 < Y입니다. 그 이유는 그 모서리의 길이가 지금까지 그 가장자리에서 발견 한 가장 낮은 것, 당신은 그 루프의 반복에서 그걸 제외 시켰습니다.