dijkstra 구현 최적화

Question

QUESTION EDITED, 지금 알고리즘을 개선하기 위해 대기열을 사용할 수 있는지 알고 싶습니다.

내가 사용하는 혼합 비용 최대 흐름 알고리즘의 구현을 발견

익스트라 :

// Implementation of min cost max flow algorithm using adjacency 
// matrix (Edmonds and Karp 1972). This implementation keeps track of 
// forward and reverse edges separately (so you can set cap[i][j] != 
// cap[j][i]). For a regular max flow, set all edge costs to 0. 
// 
// Running time, O(|V|^2) cost per augmentation 
//  max flow:   O(|V|^3) augmentations 
//  min cost max flow: O(|V|^4 * MAX_EDGE_COST) augmentations 
//  
// INPUT: 
//  - graph, constructed using AddEdge() 
//  - source 
//  - sink 
// 
// OUTPUT: 
//  - (maximum flow value, minimum cost value) 
//  - To obtain the actual flow, look at positive values only. 

#include <cmath> 
#include <vector> 
#include <iostream> 

using namespace std; 

typedef vector<int> VI; 
typedef vector<VI> VVI; 
typedef long long L; 
typedef vector<L> VL; 
typedef vector<VL> VVL; 
typedef pair<int, int> PII; 
typedef vector<PII> VPII; 

const L INF = numeric_limits<L>::max()/4; 

struct MinCostMaxFlow { 
    int N; 
    VVL cap, flow, cost; 
    VI found; 
    VL dist, pi, width; 
    VPII dad; 

    MinCostMaxFlow(int N) : 
    N(N), cap(N, VL(N)), flow(N, VL(N)), cost(N, VL(N)), 
    found(N), dist(N), pi(N), width(N), dad(N) {} 

    void AddEdge(int from, int to, L cap, L cost) { 
    this->cap[from][to] = cap; 
    this->cost[from][to] = cost; 
    } 

    void Relax(int s, int k, L cap, L cost, int dir) { 
    L val = dist[s] + pi[s] - pi[k] + cost; 
    if (cap && val < dist[k]) { 
     dist[k] = val; 
     dad[k] = make_pair(s, dir); 
     width[k] = min(cap, width[s]); 
    } 
    } 

    L Dijkstra(int s, int t) { 
    fill(found.begin(), found.end(), false); 
    fill(dist.begin(), dist.end(), INF); 
    fill(width.begin(), width.end(), 0); 
    dist[s] = 0; 
    width[s] = INF; 

    while (s != -1) { 
     int best = -1; 
     found[s] = true; 
     for (int k = 0; k < N; k++) { 
     if (found[k]) continue; 
     Relax(s, k, cap[s][k] - flow[s][k], cost[s][k], 1); 
     Relax(s, k, flow[k][s], -cost[k][s], -1); 
     if (best == -1 || dist[k] < dist[best]) best = k; 
     } 
     s = best; 
    } 

    for (int k = 0; k < N; k++) 
     pi[k] = min(pi[k] + dist[k], INF); 
    return width[t]; 
    } 

    pair<L, L> GetMaxFlow(int s, int t) { 
    L totflow = 0, totcost = 0; 
    while (L amt = Dijkstra(s, t)) { 
     totflow += amt; 
     for (int x = t; x != s; x = dad[x].first) { 
     if (dad[x].second == 1) { 
      flow[dad[x].first][x] += amt; 
      totcost += amt * cost[dad[x].first][x]; 
     } else { 
      flow[x][dad[x].first] -= amt; 
      totcost -= amt * cost[x][dad[x].first]; 
     } 
     } 
    } 
    return make_pair(totflow, totcost); 
    } 
}; 

내 질문 : http://www.stanford.edu/~liszt90/acm/notebook.html#file2

곧 그것이 인터넷 공간에서 분실하는 경우 여기에 붙여 넣습니다 Dijkstra()의 우선 순위 큐를 사용하여 향상시킬 수 있는지 여부입니다. 시도했지만 제대로 작동하지 못했습니다. 실제로 나는 Dijkstra에서 모든 노드가 아닌 인접 노드를 반복해야한다고 생각합니다.

고마워요.

Answer 1

확실하게 다이 헴라의 알고리즘은 minheap을 사용하여 향상시킬 수 있습니다. 최단 경로 트리에 정점을 놓고 인접한 모든 정점을 처리 (즉, 레이블 지정) 한 후에는 트리에 아직없는 가장 작은 레이블로 정점을 선택합니다.
이것은 미니 히프가 떠오르는 곳입니다. 순차적으로 모든 정점을 스캔하는 대신 힙에서 min 요소를 추출하고 구조를 재구성합니다. O (logn) 시간 대 O (n) 시간이 걸립니다. 힙은 아직 최단 경로 트리에없는 꼭지점 만 유지하려고합니다. 그러나 레이블을 업데이트하면 힙의 정점을 어떻게 든 수정할 수 있습니다.