ページ 11

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

Posted: 2015年7月28日(火) 22:27
by chop.chop
いつもおせわになっています。

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

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

ダイクストラ法でノード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時間ほど考えましたが分かりません。どなたかよろしくお願いします。