このアルゴリズムが何を目的としているものなのか
Posted: 2015年7月28日(火) 22:27
いつもおせわになっています。
今日質問させていただくことなのですが、こういう~~を作りたいので手直しをお願いします、という類のものではありません。
あるアルゴリズムの条件文を変えた結果、そのアルゴリズムがどのような出力をするのか、ということをお聞きしたいと思います。
まず、元のアルゴリズムはダイクストラ法です。ですが、ここでは最短経路を求めるのではなく、最短距離だけで良いとします。(別にあってもかまいませんが、今回問われているのはそこではないため。また、対象とするネットワークは重みが全て正の有向グラフです)
ダイクストラ法でノードuを経由してノードvに行ったコストが少ないと判断されると、現在の最短距離r(v)を更新する、という部分は以下のようになります
この場合出力は
{s,n1,n2,...,nN}の順に{0,hoge,hoge,hoge,...,hoge}となります。
さて、これを以下のようにします。
この場合、このアルゴリズムは何をしているのでしょうか?
あるグラフに適用させてみましたが、正直よくわからない結果になりました。
1時間ほど考えましたが分かりません。どなたかよろしくお願いします。
今日質問させていただくことなのですが、こういう~~を作りたいので手直しをお願いします、という類のものではありません。
あるアルゴリズムの条件文を変えた結果、そのアルゴリズムがどのような出力をするのか、ということをお聞きしたいと思います。
まず、元のアルゴリズムはダイクストラ法です。ですが、ここでは最短経路を求めるのではなく、最短距離だけで良いとします。(別にあってもかまいませんが、今回問われているのはそこではないため。また、対象とするネットワークは重みが全て正の有向グラフです)
ダイクストラ法でノードuを経由してノードvに行ったコストが少ないと判断されると、現在の最短距離r(v)を更新する、という部分は以下のようになります
この場合出力は
{s,n1,n2,...,nN}の順に{0,hoge,hoge,hoge,...,hoge}となります。
さて、これを以下のようにします。
この場合、このアルゴリズムは何をしているのでしょうか?
あるグラフに適用させてみましたが、正直よくわからない結果になりました。
1時間ほど考えましたが分かりません。どなたかよろしくお願いします。