13

過去 4 日間、私はダイクストラのアルゴリズムを理解しようとしています。しかし、私はできません。ポイントのベクトルがあります。そこから、コスト マトリックスを作成しました。しかし、ダイクストラのアルゴリズムの作り方がわかりません。ソースはネットで入手できますが、私はコンピュータ サイエンスのバックグラウンドを持っていないため、理解できません。私はこのような機能を作ろうとしています

vector<int> dijkstra(costMatrix[][])
{
  ....
  ....
  return vector<int>pathPointindex
}

main()
{
    vector<Point> availablePoints;
    costMatrix[][]=createCostMatrix();
    vector<int> indexes=dijikstra(costMatrix)
    for(int i=0;i<indexes.size();i++)
       cout << "path points are " << availablePoints[indexes[i]] << endl;
}

誰かがあれば、コードを投稿してください。私は怠け者ではありません。しかし、私のプロジェクトは 1 日前にすでに締め切りを過ぎていました。今、私は論理を理解するという希望を失いました. 今は機能が欲しいだけです。「困っている人はまさに天使です」 .

編集：「Loki astari」の優れた回答に感謝します

4

6 に答える 6

40

ダイクストラのアルゴリズム

英語で：

これは、ポイント A からポイント B への最短ルートを見つけるためのアルゴリズムです。
計算用語では、ノードとアークで構成されるグラフへのルートを単純化します。各ノードは中間点を表し、各アークは 2 つのノードを接続し、2 つのノード間を移動するコストを表す (負ではない) 重みを持ちます。

アルゴリズムを実装するには、2 つのリストが必要です。

  • finished: 到達するための最小コストを計算した (node,cost) のセット。
  • working: チェックされた (node,cost) のソートされたリスト。

アルゴリズム：

working.addNode(Start, 0); // No cost to get to start.

for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
    // If we have already processed this node ignore it.
    if (finished.find(node))
    {    continue;
    }

    // We have just removed a node from working.
    // Because it is the top of the list it is guaranteed to be the shortest route to
    // the node. If there is another route to the node it must go through one of the
    // other nodes in the working list which means the cost to reach it will be higher
    // (because working is sorted). Thus we have found the shortest route to the node.

    // As we have found the shortest route to the node save it in finished.
    finished.addNode(node,cost);

    // For each arc leading from this node we need to find where we can get to.
    foreach(arc in node.arcs())
    {
        dest = arc.dest();
        if (NOT (finished.find(dest)))
        {
            // If the node is already in finished then we don't need to worry about it
            // as that will be the shortest route other wise calculate the cost and add
            // this new node to the working list.
            destCost = arc.cost() + cost;
            working.addNode(dest,destCost); // Note. Working is sorted list
        }
    }
}

したがって、このアルゴリズムについて考えると。ロンドンからマンチェスターに旅行しているとします。

finished = {} // empty.
working  = { (London,0) }

次のコスト マトリックスを使用します。

                  L    S    O    B    N    M    W
(L) ondon         -    50   60   100  130  -    -
(S) outhampton    50   -    70   -    -    -    -
(O) xford         60   70   -    50   -    200  -
(B) irmingham     100  -    50   -    -    80   110
(N) orwich        130  -    -    -    -    -    -
(M) anchester     -    -    200  80   -    -    80
Ne(W) castle      -    -    -    110  -    80   -

ここで、London を作業リストから (先頭にあるため) 取り出し、完了リストに配置します。次に、ロンドンに直接接続されているすべての町を作業リストに追加します。

finished = { (London,0) }
working  = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }

ワーキング セットの町を、ロンドンから拡大したバブルの外縁と考えてください。ダイクストラのアルゴリズムの仕事は、マンチェスターに到達するまでバブルを拡大し続けることです (すでに行った手順をたどることはありません)。そのため、泡は常に外側に膨張し、泡の最も小さい部分を常に膨張させます。

したがって、次のステップは、リストの先頭を取得して繰り返すことです。サウサンプトンからの目的地は 2 つだけです。ロンドン（完成したリストにあるので破棄します）とオックスフォードに戻ります。オックスフォードまでの費用は、50 + サウサンプトンからオックスフォードまでの費用です (作業リストに 2 回あることに注意してください。最適なルートではないため、後で破棄しますのでご安心ください)。

finished = { (London,0), (Southampton,50) }
working  = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }

だからループを繰り返す。リストの先頭はオックスフォードです。オックスフォードからマンチェスター（200）、バーミンガム（50）に行くか、ロンドン（60）またはサウサンプトンに戻ることができます（上記の各コストにオックスフォードに行くためのコストを追加する必要があることを思い出してください。オックスフォードからはサウサンプトンに行きましたが、すでにサウサンプトンへの最短ルートを見つけているので、処理は必要ありません) これにより、次のようになります。

finished = { (London,0), (Southampton,50), (Oxford, 60) }
working  = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}

現在、作業リストにマンチェスターが含まれていることに注意してください (これが目的地です)。しかし、もっと短いルートが見つかるかもしれないので、作業を続ける必要があります。それで今、私たちはバーミンガムから拡大しています。そこから、オックスフォード(50)、マンチェスター(80)、ロンドン(100)、ニューカッスル(110)に行くことができます。最初にバーミンガムまでの交通費を追加すると、次のようになります。

finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working  = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}

次の 2 つのノード。オックスフォードとバーミンガムはすでに終了リストにあるため、無視できます。したがって、ノリッジからマンチェスターまで 50 マイル未満のルートがない限り、その後の反復でマンチェスターに到達します。

于 2010-08-10T11:22:19.550 に答える
13

非常に実用的なアプローチを備えたTopCoderチュートリアルを参照することをお勧めします。negative edge weightsSTL プライオリティ キューがどのように機能するかを調べて、グラフに何もないことを確認する必要があります。

まともな完全な実装はここにあります。RecoverPathソースからシンクへのパス上のノードを取得するには、それにパス ベクトルを追加してメソッドを実装する必要があります。このソリューションを使用するには、次の方法でに変換する必要もありadjacency matrixますadjacency list。

for (int i=0;i<nNodes;i++)
    for (int j=0;j<nNodes;j++){
        if (costMatrix[i][j] != NO_EDGE_VALUE){
            G[i].pb(make_pair(j,costMatrix[i],[j]));
        }
    }

編集: グラフが密集している場合は、Ford Bellmanアルゴリズムを使用することをお勧めします。これははるかに単純であり、それほど遅くはなりません。

EDIT2：パスを計算するには、ヘッダーに追加する必要があります

int P[MAX]; /*array with links to parents*/
for(i=0; i<=nodes; i++) P[i] = -1; /*magic unset value*/

// dijkstra
while(!Q.empty()) {
    ....
    if(!F[v] && D[u]+w < D[v]) {
        D[v] = D[u] + w;
        /*By setting P[v] value we will remember what is the 
          previous node on path from source */
        P[v] = u; // <-- added line
        Q.push(pii(v, D[v]));
    }
    ...
}

次に、RecoverPath メソッドを追加する必要があります (パスが存在する場合にのみ機能します)。

vector<int> RecoverPath(int src, int dest){
    vector<int> path;
    int v = dest;
    while (v != src) {
        path.push_back(v);
        v = P[v];
    }
    path.push_back(src);
    std::reverse(path.begin(),path.end());
    return path;
}
于 2010-08-10T09:35:03.693 に答える
2

ダイクストラ アルゴリズムの主な考え方はかなり単純です。特定の点 A への既知の最短経路を持つ点のセットがあるとします。次に、新しい点 C をセットに追加するとします。追加したいポイントに接続されているポイントをセットから見つけてみましょう。それをポイントの B(i) とします。したがって、すべてのポイントの B(i) について、A から B(i) まで、および B(i) と C の間の距離の合計を求めることができます。その距離の最小値は、間の最小値になります。 A と C。

于 2012-08-06T14:37:05.180 に答える
1

c++での実装

#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.insert( mp(0, 1) );

    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
            d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
    }
}

int main(void)
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int i, a, b, c;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= M; i++)
        scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);

    solve();

    for(i = 2; i <= N; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}
于 2010-08-10T14:07:09.240 に答える
0 
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>


using namespace std;

const size_t INT_MAX = 0xFFFFFFFF; // or any other value representing infinite distance.

最初に、ソース ノード インデックス、宛先ノード インデックス、およびエッジの「重み」( length ) を含む構造体エッジを作成します。

struct edge { size_t from; size_t to; size_t length; };

隣接する隣人へのエッジを含むクラス Node を定義します。

class Node 
{ 
public:
    void AddNeighborEdge( edge _NeighborEdge ) { m_neighborsEdges.push_back( _NeighborEdge ); } 
    vector<edge>::iterator FirstNeighborEdge() { return  m_neighborsEdges.begin(); }
    vector<edge>::iterator LastNeighborEdge() { return  m_neighborsEdges.end(); }

private: 
     vector<edge>  m_neighborsEdges; 
};

クラス NeighborsDistanceUpdator は、for_each アルゴリズムによって「ファンクター」として使用され、グラフ内の現在のノードから隣接する隣接ノードまでの最小距離の反復パスおよび更新のために使用されます。

class NeighborsDistanceUpdator
{
public:
    NeighborsDistanceUpdator( vector<size_t>& _min_distance_from_source, queue< size_t >& _nodes_to_visit ) : m_min_distance_from_source( _min_distance_from_source ),                                                              m_nodes_to_visit( _nodes_to_visit ) 
                                                            {} 
    void operator()( edge& _edge )
    {   
        size_t from = _edge.from;
        size_t to = _edge.to;

        if ( m_min_distance_from_source[ to ] > m_min_distance_from_source[ from ] + _edge.length ) 
        {
            m_min_distance_from_source[ to ] = m_min_distance_from_source[ from ] + _edge.length;
            m_nodes_to_visit.push( to );
        }
    }    

private:
    vector<size_t>& m_min_distance_from_source;
    queue< size_t >& m_nodes_to_visit;
};

ダイクストラ アルゴリズムに関しては、グラフ内のすべてのノードを実行し、ノードごとにソースからの最小距離を更新し (小さい場合)、隣接するノードを保存して訪問します。 

size_t dijkstra( map< size_t, Node  >& _graph, size_t _sourceIndex, size_t _targetIndex ) 
{
    vector<size_t> min_distance_from_source( _graph.size(), INT_MAX );
    min_distance_from_source[ _sourceIndex ] = 0;
    queue< size_t > nodes_to_visit;
    nodes_to_visit.push( _sourceIndex );
    NeighborsDistanceUpdator neighborsDistanceUpdator( min_distance_from_source, nodes_to_visit );

    while ( ! nodes_to_visit.empty() ) 
    {

        size_t currNodeIndex = nodes_to_visit.front();

        if ( currNodeIndex ==  _targetIndex ) return min_distance_from_source[ currNodeIndex ];

        nodes_to_visit.pop();

        vector<edge>::iterator firstNeighborEdge= _graph[ currNodeIndex ].FirstNeighborEdge();
        vector<edge>::iterator lastNeighborEdge= _graph[ currNodeIndex ].LastNeighborEdge();

        for_each( firstNeighborEdge, lastNeighborEdge, neighborsDistanceUpdator );
    }
    return INT_MAX;
}

テスト...

int main()
{
    Node node1;
    Node node2;
    Node node3;
    Node node4;

    map< size_t, Node > graph;
    edge ed;

    ed.from = 0;
    ed.to = 1;
    ed.length = 1;
    node1.AddNeighborEdge( ed );

    cout << "node: " << 0 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 0;        
    ed.to = 2;
    ed.length = 4;
    node1.AddNeighborEdge( ed );
    graph.insert( make_pair( 0, node1 ) );

    cout << "node: " << 0 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 1;
    ed.to = 2;
    ed.length = 1;
    node2.AddNeighborEdge( ed );

    cout << "node: " << 1 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 1;
    ed.to = 3;
    ed.length = 3;
    node2.AddNeighborEdge( ed );
    graph.insert( make_pair( 1, node2 ) );

    cout << "node: " << 1 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 2;
    ed.to = 3;
    ed.length = 1;
    node3.AddNeighborEdge( ed );
    graph.insert( make_pair( 2, node3 ) );

    cout << "node: " << 2 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 3;
    ed.to = INT_MAX;
    ed.length = INT_MAX;
    node3.AddNeighborEdge( ed );
    graph.insert( make_pair( 3, node4 ) );

    cout << "node: " << 2 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;


    cout << "min length from: 1 to 4 = " << dijkstra( graph, 0,3  ) << endl;
}
于 2017-01-08T01:20:50.050 に答える