2

QUESTION EDITED、今はキューを使用してアルゴリズムを改善できるかどうかだけを知りたいです。

ダイクストラを使用する混合コスト最大フローアルゴリズムのこの実装を見つけました：http：//www.stanford.edu/~liszt90/acm/notebook.html#file2

インターネットで紛失した場合に備えて、ここに貼り付けます。

// 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);
  }
};

私の質問は、Dijkstra（）内の優先キューを使用して改善できるかどうかです。試しましたが、うまく動作しませんでした。実際、ダイクストラでは、すべてのノードではなく、隣接するノードをループしているはずです...

どうもありがとう。

4

2 に答える 2

1

確かに、ダイクストラのアルゴリズムは、minheapを使用することで改善できます。頂点を最短経路ツリーに配置し、隣接するすべての頂点を処理（つまりラベル付け）した後、次のステップは、まだツリーにない最小のラベルを持つ頂点を選択することです。
ここでminheapが思い浮かびます。すべての頂点を順番にスキャンするのではなく、ヒープからmin要素を抽出して再構築します。これには、O（logn）時間とO（n）の時間がかかります。ヒープは、最短経路ツリーにまだ含まれていない頂点のみを保持することに注意してください。ただし、ラベルを更新すれば、ヒープ内の頂点をなんとかして変更できるはずです。

于 2014-02-13T11:12:13.490 に答える
1

優先度付きキューを使用してダイクストラのアルゴリズムを実装すると、実際に実行時間が改善されるかどうかはわかりません。優先度付きキューを使用すると、ソースからの距離が最小の頂点を見つけるために必要な時間が短縮されるためです（O（log V）優先キューとナイーブ実装のO（V））、新しいエッジの処理に必要な時間も増加します（優先キュー付きのO（log V）とナイーブ実装のO（1））。

したがって、単純な実装の場合、実行時間はO（V ^ 2 + E）です。

ただし、優先キューの実装の場合、実行時間はO（V log V + E log V）です。

非常に密なグラフの場合、EはO（V ^ 2）になる可能性があります。つまり、ナイーブ実装の実行時間はO（V ^ 2 + V ^ 2）= O（V ^ 2）であり、優先キューの実装の実行時間はO（V log V + V ^ 2 log V）= O（V ^ 2 log V）。したがって、ご覧のとおり、密グラフの場合、優先キューの実装の実行時間は実際には最悪の場合に悪化します。

上記の実装を書いている人々が隣接リストを使用するのではなく隣接行列としてエッジを保存しているという事実を考えると、このコードを書いた人々はグラフがO（V ^ 2）エッジを持つ密グラフであることを期待していたようです。したがって、ここでは優先キューの実装よりも単純な実装を使用するのが理にかなっています。

ダイクストラのアルゴリズムの実行時間の詳細については、このウィキペディアのページを参照してください。

于 2019-10-27T14:52:00.360 に答える