グラフを入力できません

Question

C++でhttp://www.spoj.com/problems/SHOP/の問題を解決していますが、グラフを入力してDijkstraアルゴリズムを適用する方法を理解することができません。 ここグラフでformat-
X 1 S 3
4 2 X 4
X 1 D 2

最初の行は、列をグリッドの&行
"S" &を示し"D" - 送信元と宛先をrespetively指定します。
Numbers - そのブロックを通過するのに必要な時間を示します。 "X" - 入力なしゾーンを示します。
HOwはDIjkstraアルゴリズムの必要に応じてノードとエッジで次のグラフを変換します。マップをグラフに変換する方法はわかりません。

Answer 1

変換する必要はありません。あなたはある時点（i、j）にいると想像してください。 （私は各四角形から4つの動きが許されていると仮定します）。

1）そのインデックスが内部にある場合は、（i + 1、j）、（i、j + 1）、（i-1、j）、テーブル 2）そのインデックスにはX

のマークがついていません。したがって、あなたのダイクストラアルゴリズムに正方形Sの位置を与えます。また、データ構造に新しい正方形のセットを追加するたびに、 Dの位置に達すると、それを印刷します。

さらに、この問題は私には重み付けされていないように見えるので、キューを使用して単純なBFSを使用することもできます。しかし、あなたがダイクストラを使い、異なる広場に行くことが異なるコストを持っている場合。キューの代わりにプライオリティキューを使用します。 はたとえば、あなたはこのように、設定されたデータ構造を使用することができます。

int dist[][]; // this contains the cost to get to some square 
//dist is initialized with a large number 

struct node{ 
    int i, j; //location 
    node(int ii, int jj){ 
     i = ii; 
     j = jj; 
    } 

    bool operator < (node &n)const{ //set in c++ will use this to sort 
     if(dist[i][j] == dist[n.i][n.j]) return i < n.i || j < n.j; //this is necessary 
     return dist[i][j] < dist[n.i][n.j]; 
    } 
}; 

set <node> q; 

int main(){ 
    //initialized dist with large number 
    dist[S.i][S.j] = 0; //we start from source 
    q.push(node(S.i, S.j)); 
    while(true){ 
     //pick the first element in set 
     //this element has the smallest cost 
     //update dist using this node if necessary 
     //for every node that you update remove from q and add it again 
     //this way the location of that node will be updated in q 
     //if you see square 'D' you are done and you can print dist[D.i][D.j] 
    } 

    return 0; 
} 

Answer 2

ノードをノードとエッジに変換する必要はありません。 （行番号、列番号、時刻）を含む構造体を作ることができます。ここで、timeは、この座標にソースからどのくらいの時間を掛かるかを表します。今度はこの構造体の最小のヒープを時間のキーで作ります。 minヒープから要素を抽出し（最初はソースは時間が0のminヒープになります）、抽出された要素trueを訪問したminヒープ（訪問していない要素とXを含まない要素のみ）に隣接する要素をプッシュします。このように、抽出された要素は宛先ではありません。