この経路の距離である。方が小さければその値が設定される。負の重みの閉路がないなら、それぞれの最短経路には各頂点は高々1回出現する。至ったとき、それ以上の経路や距離の短縮は不可能である。任意の閉路について、次が成り立つ。項は相殺され、次の式が残る。総和すなわち、全ての閉路は負でない重みを持つ。距離ベクトル型ルーティングプロトコルで使われている。内の複数のノード(ルーター)が関与するためである。これは次のステップで構成される。各ノードは自身とAS内の他の全ノードとの距離を計算し、その情報をテーブルに格納する。各ノードはそのテーブルを隣接する全ノードに送る。隣接ノードから距離テーブルを受け取ると、他の全ノードへの最短経路を計算し、自身のテーブルを適宜更新する。このときのベルマン-フォード法の主な欠点は次の通りである。スケーラビリティが良くない。ネットワーク構成に変更があった場合、ノードからノードへと伝達されるため、すぐには反映されない。無限に数えてしまう(リンクやノードの障害によって、他のノードから到達不能なノードが生じた場合、到達できない部分への推定距離を増大させる処理が無限に続く可能性があり、その間ルーティング上のループが生じ得る)。Yenによる改良[編集]1970年、Yenはベルマン-フォード法の改良を発表した[3]。Yenの改良は、まず全頂点に何らかの線型な順序を割り当て、全辺の集合を2つの部分集合に分割する。