数学ナビゲーター掲示板

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

[ 最新記事及び返信フォームをトピックトップへ ]

■50382 / inTopicNo.1)  最小費用流問題
  
□投稿者/ jun 一般人(1回)-(2020/06/21(Sun) 17:24:59)

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

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

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



トピック内ページ移動 / << 0 >>

このトピックに書きこむ

Mode/  Pass/

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

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