最短経路問題を1つ算出するスクリプト

お世話になります。
以下のようなファイルを利用して、最短経路を求めるスクリプトをご教示いただけないでしょうか。
Metricがもっともすくないものが良。

可能な限りC言語以外で実現したいと考えております。
## 検索してみたのですが、どうもC言語のプログラムが多そうです。


(snip)
SourceDestMetric
121
131
415
434
451
461
475
484
492
4107
4116
41214
4139
41412
41523
41627
41720
18191
1974
20184
20192
21192
242
231
272
・・・・・・
・・・・・
・・・・
・・・
・・
(snip)

No.4 回答者： Tacosan 回答日時： 2007/12/04 23:48

source/dest/metric などの情報をどのように入手するかは全く考えていません. 最終的に $metric{$i}{$j} に $i から $j への metric が入っていれば OK です.

ああ, 1点言っておくべきことがあります. 実際にはこれは「最短経路」を見つけていないので, 「最短経路」を見つけるためにはもうちょっと処理が必要です. $dist{$i}{$j} を更新するときに $via{$i}{$j} = $k も実行して, 「$i から $j への最短経路は $k を通る」ということを記録しておくんでしょう.

No.3 回答者： Tacosan 回答日時： 2007/12/03 20:37

ちょいと調べましたら, Warshall-Floyd あたりが安全そうです.

ある程度プログラムが書けるなら調べたものをプログラムにした方がよいと思いますが一応 Perl で. $metric{$i}{$j} が $i から $j への metric とします (存在しなければ undef). あと, $n がソース (デスティネーションでも同じだけど) の個数です:
my %dist;
for my $i (1 .. $n) {
for my $j (1 .. $n) {
$dist{$i}{$j} = $metric{$i}{$j};
}
$dist{$i}{$i} = 0;
}

for my $k (1 .. $n) {
for my $i (1 .. $n) {
for my $j (1 .. $n) {
# Calculate the distance from $i to $j with at most $k hops
my $s = (defined $dist{$i}{$k} && defined $dist{$k}{$j}) ? $dist{$i}{$k} + $dist{$k}{$j} : undef;
if (! defined $dist{$i}{$j} || (defined $s && $s < $dist{$i}{$j})) {
$dist{$i}{$j} = $s;
}
}
}
}
多分動くと思うけど, あんまり自信なし. ちなみに, n^3 くらいの時間がかかります.

この回答へのお礼

ご親切にどうもありがとうございます。
このスクリプトですが、"Source Dest Metric"等の情報を外部ファイルとして取り込む必要があるのでしょうか。

(snip)
Source Dest Metric
1 2 1
1 3 1
・・・
(snip)

お礼日時：2007/12/04 19:46

No.2 回答者： Tacosan 回答日時： 2007/12/03 13:48

ああ, 「1点から他の点への最短経路」と「全点間の最短経路」ではアルゴリズムが違う (同じでもいいんだけど変えた方が効率的) ので, どちらかによって方針が変わります.

「1点から他の点への最短経路」だと Dijkstra のアルゴリズムがいいと思います. それほど難しくありませんし, ほぼベストに近い時間でできると思います.
「全点間の最短経路」の方は, Dijkstra のアルゴリズムを繰り返してもいいけど他にもやりかたはあったはずです. 忘れましたが.
そうそう, 言語を決めてもらえると話が楽になります.

この回答へのお礼

なるほどです。勉強になります。
言語は非コンパイル言語であれば、何でも良いと思っております。
PERL,SHELLとかのスクリプトで実現可能でしょうか。

「全点間の最短経路」を見つけたいと思っております。
参考サイトとかないでしょうか。。

お礼日時：2007/12/03 14:40

No.1 回答者： Tacosan 回答日時： 2007/11/30 18:45

「できれば C 以外」という理由がよくわからんのだけど, 「C で書かれたものを別の言語にコンバートする」のはダメ?

metric に負のものがなければ Dijkstra の方法でできそうなんだけど, どうやって優先順位キュー (ヒープ) を作りますかねぇ.

この回答へのお礼

"C"で書かれたものを別の言語にコンバートすることでも、問題ありません。「できれば C 以外」というのは、私が理解できない分野なので、、、すみません。
metricに負の値ものはありません。

Bestな経路が1つ抽出されれば良いのですが、むずかしそうですね。

お礼日時：2007/12/03 10:12