5

私は、ダイクストラアルゴリズムのCでのこの実装を理解しようとしていたと同時に、2つの特定のノード（送信元と宛先）間の最短パスのみが見つかるように変更しました。

しかし、私は正確に何をすべきかわかりません。私の見方では、何もすることはありません。これらの配列を変更しd[]たり、最短経路計算のためにいくつかの重要なデータを集約したりすることはできないようです。prev[]

私が考えることができる唯一のことは、パスが見つかったときにアルゴリズムを停止することです。つまり、mini = destination訪問済みとしてマークされたときにサイクルを中断します。

それを改善するために私ができることは他にありますか、それともそれで十分ですか？

編集：
私に与えられた提案に感謝しますが、人々はまだ私が質問したことを正確に答えることができません。私が知りたいのは、2つのノード間の最短パスのみを検索するようにアルゴリズムを最適化する方法です。今のところ、他のすべての一般的な最適化には興味がありません。私が言っているのは、ノードXから他のすべてのノードへのすべての最短パスを見つけるアルゴリズムで、特定のパスのみを検索するように最適化するにはどうすればよいですか？

forPS：ループが1までで始まることに気づきましたが<=、なぜそれがで始まり、まで続くことができないの0です<か？

4

3 に答える 3

5

あなたの質問の実装は隣接行列を使用しており、これがO（n ^ 2）の実装につながります。実世界のグラフは通常まばらである、つまりノードの数nは通常非常に多いことを考えると、エッジの数はn^2からはるかに少なくなります。

ヒープベースのダイクストラ実装を検討することをお勧めします。

ところで、単一ペアの最短経路は、特定のノードからの最短経路よりも速く解決することはできません。

#include<algorithm>
using namespace std;

#define MAXN 100
#define HEAP_SIZE 100
typedef int Graph[MAXN][MAXN];

template <class COST_TYPE>
class Heap
{
public:
    int data[HEAP_SIZE],index[HEAP_SIZE],size;
    COST_TYPE cost[HEAP_SIZE];
    void shift_up(int i)
    {
        int j;
        while(i>0)
        {
            j=(i-1)/2;
            if(cost[data[i]]<cost[data[j]])
            {
                swap(index[data[i]],index[data[j]]);
                swap(data[i],data[j]);
                i=j;
            }
            else break;
        }
    }
    void shift_down(int i)
    {
        int j,k;
        while(2*i+1<size)
        {
            j=2*i+1;
            k=j+1;
            if(k<size&&cost[data[k]]<cost[data[j]]&&cost[data[k]]<cost[data[i]])
            {
                swap(index[data[k]],index[data[i]]);
                swap(data[k],data[i]);
                i=k;
            }
            else if(cost[data[j]]<cost[data[i]])
            {
                swap(index[data[j]],index[data[i]]);
                swap(data[j],data[i]);
                i=j;
            }
            else break;
        }
    }
    void init()
    {
        size=0;
        memset(index,-1,sizeof(index));
        memset(cost,-1,sizeof(cost));
    }
    bool empty()
    {
        return(size==0);
    }
    int pop()
    {
        int res=data[0];
        data[0]=data[size-1];
        index[data[0]]=0;
        size--;
        shift_down(0);
        return res;
    }
    int top()
    {
        return data[0];
    }
    void push(int x,COST_TYPE c)
    {
        if(index[x]==-1)
        {
            cost[x]=c;
            data[size]=x;
            index[x]=size;
            size++;
            shift_up(index[x]);
        }
        else
        {
            if(c<cost[x])
            {
                cost[x]=c;
                shift_up(index[x]);
                shift_down(index[x]);
            }
        }
    }
};



int Dijkstra(Graph G,int n,int s,int t)
{
    Heap<int> heap;
    heap.init();
    heap.push(s,0);
    while(!heap.empty())
    {
        int u=heap.pop();
        if(u==t)
            return heap.cost[t];
        for(int i=0;i<n;i++)
            if(G[u][i]>=0)
                heap.push(i,heap.cost[u]+G[u][i]);
    }
    return -1;
}
于 2010-04-17T03:18:29.680 に答える
2

個別のオープンリストとクローズドリスト（訪問済みと未訪問）を維持することで、シーク時間を少し改善できる可能性があります。

現在、ソースまでの距離が最も短い未訪問のノードを検索しています。

1）個別の「オープン」リストを維持することができます。このリストは、反復するにつれてますます小さくなり、検索スペースが徐々に小さくなります。

2）「クローズド」リスト（アクセスしたノード）を維持している場合は、それらのノードのみに対して距離を確認できます。これにより、検索スペースが徐々に増加しますが、反復ごとにすべてのノードをチェックする必要はありません。まだ訪問されていないノードに対する距離チェックには目的がありません。

また、評価する次のノードを選択するときは、グラフに従うことを検討してください。「閉じた」リストで、最小の距離を探し、その接続の中から「開いた」ノードを検索できます。（ノードの接続に開いているノードがないことが判明した場合は、閉じたリストからノードを削除できます。行き止まりです）。この接続を使用してオープンリストを作成することもできます。これは島にも役立ちます（グラフに島がある場合、コードは現在クラッシュします）。

可能なすべてのノードの組み合わせを含むクロステーブルの代わりに、より効率的な接続グラフを事前に作成することもできます（たとえば、neighbours []ノードリストを持つノード構造体）。これにより、dist[][]配列内の各ノードのすべてのノードをチェックする必要がなくなります。

すべてのノード距離を無限大に初期化する代わりに、ターゲットまでの「可能な限り最小の楽観的距離」に初期化し、それに基づいてノード処理を優先することができます（ノードが2D平面上にある場合は、鳥の距離を使用できます。 ）。ヒューリスティックについては、A*の説明を参照してください。私はかつてこれをキューの周りに実装しましたが、このコードにどのように統合するのか完全にはわかりません（キューがない場合）。

于 2010-04-17T00:45:07.113 に答える
1

ダイクストラに対してできる最大の改善点は、代わりにA*を使用することです。もちろん、これにはヒューリスティック関数が必要です。

于 2010-04-17T03:10:20.127 に答える