正の重みを持つ無向グラフが与えられた場合、ロックされたエッジとロックされていないエッジの 2 種類のエッジがあります。特定のエッジがロックされているかロックされていないエッジであるかを判断するには、O(1) かかります。
与えられた 2 つの頂点s、tおよび正の数k = O(1) に対して、最大でk 個のロックされたエッジを含むsとtの間の最短経路をどのように見つけることができますか?
与えられた 2 つの頂点s、tおよび正の数k = O(1) に対して、正確にk 個のロックされたエッジを含むsとtの間の最短パスを見つけるにはどうすればよいでしょうか?
このグラフでダイクストラ アルゴリズムを実行して、指定された頂点間の最短パスを見つける方法と、無向グラフを有向グラフに変換する方法がわかりません。