数学ナビゲーター掲示板
HOME
HELP
新規作成
新着記事
ツリー表示
スレッド表示
トピック表示
発言ランク
ファイル一覧
検索
過去ログ
ツリー一括表示
最小費用流問題
/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
数学ナビゲーター