私の講師は次のように述べています。
• ループ 1 の 1 回の反復の実行時間を減らすようにしてください。効果的なリラックス操作を提供できるエッジのみを考慮してください。
• d[v] が最後に減少してから、v から出るエッジが緩和されていない場合、頂点 v はアクティブです。
• アクティブな頂点から出ているエッジに対してのみ RELAX を実行します。
• Queue データ構造にアクティブな頂点を格納します。
私の質問は、FIFO キューが Bellman-Ford の反復をどのように高速化するかということです。どのような状況で「エンキュー」しますか?
キューが存在するのは、アクティブなノードを追跡するのに便利なデータ構造だからです。
ノードに接続されているエッジを最初に緩和しようとするときに、そのノードをキューに入れます。ノードに到達するまでに、アクティブなネイバーからそのノードへのすべてのエッジが緩和されます。
これらの手順を実行すると、Bellman-Ford アルゴリズムがDijksta のアルゴリズムに近いものに変換されます。
ノードがアクティブな場合は、次の検討対象になります。また、知っておく必要があるすべてのノードをすでに決定しているノードも訪問しました。そして、まだ到達していないノードはunvisitedです。
3 つのステータスを色と考えることができます。最初のノードだけがアクティブに色付けされ、他のすべてのノードはアクセスされていない状態から始めます。移動すると、アクティブな色が外側に移動し、訪問したノードを囲む境界線が形成されます。アクティブなノードがなくなったら完了です。すべてがVisited の色になります。
キューの代わりに、2 つのリストを使用できます。最初のリストには、現在検討中のアクティブノードと、2 番目のリストに追加した新しいアクティブノードが含まれます。最初のリストが使い果たされたら、それを空にして、2 つのリストを交換します。代わりに単一のキューを使用すると、現在の反復と次の反復の間に明確な境界線を持たないようにすることで、反復をブレンドします。