miscalc https://blog.hatena.ne.jp/miscalc/ miscalc のブログ https://miscalc.hatenablog.com/ 概要 通常の最短経路問題と違って、辺を通ったときのコストの変化のしかたが変な場合でも、ダイクストラ法で解けることがある。ダイクストラ法を適用できる条件は 「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらない 「辺を通ったことでコストが減る」ということが起こらない （通常の）最短経路問題とダイクストラ法 （通常の）最短経路問題は、次のような問題です。 グラフがある。グラフの各辺には 重み とよばれる値が設定されている。 番目の辺の重みを とする。 あなたは頂点 にいる。また、コスト とよばれる値を持っている（最初のコストは である）。「今いる頂点を始点にもつ辺… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmiscalc.hatenablog.com%2Fentry%2F2022%2F10%2F10%2F115348" title="コスト変化が変なときのダイクストラ法 - miscalc のブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2022-10-10 11:53:48 rich https://miscalc.hatenablog.com/entry/2022/10/10/115348 1.0 100%