このアルゴリズムが何を目的としているものなのか

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
chop.chop
記事: 36
登録日時: 4年前

このアルゴリズムが何を目的としているものなのか

#1

投稿記事 by chop.chop » 4年前

いつもおせわになっています。

今日質問させていただくことなのですが、こういう~~を作りたいので手直しをお願いします、という類のものではありません。
あるアルゴリズムの条件文を変えた結果、そのアルゴリズムがどのような出力をするのか、ということをお聞きしたいと思います。

まず、元のアルゴリズムはダイクストラ法です。ですが、ここでは最短経路を求めるのではなく、最短距離だけで良いとします。(別にあってもかまいませんが、今回問われているのはそこではないため。また、対象とするネットワークは重みが全て正の有向グラフです)

ダイクストラ法でノードuを経由してノードvに行ったコストが少ないと判断されると、現在の最短距離r(v)を更新する、という部分は以下のようになります

コード:

if(r(v)>r(u)+w(u,v))//w(u,v)はu,v間の重み
{
     r(v)=r(u)+w(u,v);
}
この場合出力は
{s,n1,n2,...,nN}の順に{0,hoge,hoge,hoge,...,hoge}となります。

さて、これを以下のようにします。

コード:

if(r(v)>max(r(u),w(u,v)))//w(u,v)はu,v間の重み,max(A,B)はAとBの大きいほうを返す関数
{
     r(v)=max(r(u),w(u,v))
}
この場合、このアルゴリズムは何をしているのでしょうか?
あるグラフに適用させてみましたが、正直よくわからない結果になりました。

1時間ほど考えましたが分かりません。どなたかよろしくお願いします。

“C言語何でも質問掲示板” へ戻る