私は現在、次のことを要求される宿題に取り組んでいます。
バイナリ ヒープを使用した単一ソース最短経路問題に対する DIJKSTRA のアルゴリズムを実装します。実行時間は O(ElogV) である必要があります。
簡単です！ただし、問題はコードで解決する必要があります。これまでは、それほど難しい概念ではありません。
プログラムはファイルからデータを読み取り (以下のサンプルを参照)、ノード 0 から各ノードまでの最短パスの長さの合計を 1 つの数値として出力する必要があります。入力フォーマット: 以下の各ファイルの最初の行には、グラフ内の頂点の数とエッジの数が含まれています (「n=XXXX m=XXXXX」の形式)。ファイルの残りの部分は、次のように編成されています。各頂点 i が 1 行に表示され、その後に i の隣接 j>i (j とエッジの長さ (i,j) を含む) の行が続きます。ネイバーの各リストは、空の行で終了します。i より大きいインデックスを持つ隣接頂点を持たない頂点 i は表示されません。注: 頂点には 0 から n-1 までのインデックスが付けられます。注: 各エッジは、小さい方のエンドポイントで 1 回だけ言及されます。 サンプル入力: 1.最初の入力 2.2 番目の入力 の最短パス ツリーの長さは、それぞれ 10721073 と 625349 である必要があります。プログラムは、最初の入力では 3 ～ 10 秒、2 番目の入力では 1 秒未満で出力を返す必要があります。
私の質問:ファイルの形式とコードでの変換方法に関する教授の説明がよくわかりません。視覚化する必要があるグラフの種類もわかりません。二分木で最短経路を見つけているのでしょうか、それとも多くの頂点と辺を持つグラフ (二分木ではない) で最短経路を見つけているのでしょうか? (彼が Binary Heaps について言及しているため、私は混乱しているため、ここで何を視覚化すればよいかわかりません)
よくわからないファイルについて:グラフを見ると、次のようになっています。
n=25000 m=576014
0
176 67
665 185
1129 26
1414 114
1748 205
2027 264
2714 212
2743 132 ...
n = number of vertices彼の説明から、それとm = number of edges. 私が理解していないのは、頂点の後の数値のペアが、0ダイクストラのオンを使用することになっているグラフに関して何を表しているかです。また、いずれかのファイルの末尾を見ると、この形式でリストされている頂点の数が、n ='s. どうしてこれなの？