数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

ツリー一括表示

Nomal 最小費用流問題 /jun (20/06/21(Sun) 17:24) #50382


親記事 / 返信無し
■50382 / 親階層)  最小費用流問題
□投稿者/ jun 一般人(1回)-(2020/06/21(Sun) 17:24:59)

    大学2年でグラフ理論を学んでいるものです。
    最小費用流問題の解法として、プリマルデュアル法を使います。
    ここで質問があります。
    プライマルデュアル法では最短路の計算をDijkstraで行うと思うのですが、残余ネットワークの各枝のコスト(費用)はマイナスの値をとってしまうと思うのですがこの場合Dijkstraを用いても正しい解が得られるのでしょうか。

    それとも、枝の容量が負の値をとっていないから問題ないのでしょうか。

    参考にした資料は「プライマルデュアル法 最小費用流問題」と検索したら出てくる「TOKYO TECH OCW」さんのPDFを参考にしました。
    このpdfでは、コスト(費用)が最小のルートをDijkstraで探しており残余ネットワークにおいてコスト(費用)が負になっているのが問題ないのかという質問です。
[ □ Tree ] 返信/引用返信 [メール受信/OFF] 削除キー/


Mode/  Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター