私は重み関数wを持つグラフG（V、E）を向けました。各（u、v）の重みは正の値となる。頂点k 'がグラフの中で最も軽い円を見つける必要があります。特定の頂点を通る有向グラフの中で最も軽量な円
また、私は（私は一度だけ、それを使用することができます）陽性の重みを持つグラフの最も軽量なパスを見つけることができた使用することができるアルゴリズムを与えてくれました。
私はすべての頂点と辺を強くコンポーネントに接続されているサブグラフG」を作成考えました。 k 'がその一部であるグラフを見つける。 k 'からいくつかのvの頂点までの最も軽い隣接する辺を見つける。それから私は与えられたアルゴリズムを実行し、軽量のパスを見つけて、欠落した頂点の重み（（k '、v））を加えます。
は正しいですか？私はこのコースの始めにいて、私はまだそこにいないと感じています。
...グーグルで開始することができ、この定義を考えます。とにかく...
はK」と同じ、発信エッジを持つワット新しいvetrex を追加します。
その後K」〜ワットからの最短経路を見つけるために、ダイクストラのアルゴリズムを使用しています。
代替K 'パスでワットため、あなたはKを含む最小のサイクルを持っています'。
それはあなたが解決策としてk->k自己ループを除外単一ソースの最短経路問題、であり、kにkから長いパスを見つけます。トリックは常に最短パスのスレッドを展開します。
非常に興味深い問題です。グラフに負の値がないと仮定しています。そうでなければ、負の値が少なくとも0になるように頂点を正規化する必要があります。最初の方法は、ターゲットの頂点から始まるすべてのサイクルを検出することです（k ）。その後、これらのサイクルのすべての重みを計算し、最小値を取る。第2の方法は、ターゲットノード（k）からDijkstraアルゴリズム（負の重みを再び注意深く見る）を実行することである。次に、（k）のすべての入力エッジを反復し、最小ダイクストラ値を有するソースノードを選択する。現在、最も軽いサイクルには、（k）から選択されたノード+（k）に戻るためのブリッジまでの単一パス（ダイクストラトラバーサルによって形成される）が含まれます。私は助けることを願っています:)