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

質問

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

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

(snip)
Source Dest Metric
1 2 1
1 3 1
4 1 5
4 3 4
4 5 1
4 6 1
4 7 5
4 8 4
4 9 2
4 10 7
4 11 6
4 12 14
4 13 9
4 14 12
4 15 23
4 16 27
4 17 20
18 19 1
19 7 4
20 18 4
20 19 2
21 19 2
2 4 2
2 3 1
2 7 2
・・・・・・
・・・・・
・・・・
・・・
・・
(snip)

回答No.4

Tacosan

source/dest/metric などの情報をどのように入手するかは全く考えていません. 最終的に $metric{$i}{$j} に $i から $j への metric が入っていれば OK です.
ああ, 1点言っておくべきことがあります. 実際にはこれは「最短経路」を見つけていないので, 「最短経路」を見つけるためにはもうちょっと処理が必要です. $dist{$i}{$j} を更新するときに $via{$i}{$j} = $k も実行して, 「$i から $j への最短経路は $k を通る」ということを記録しておくんでしょう.

回答No.3

Tacosan

ちょいと調べましたら, 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)

回答No.2

Tacosan

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

お礼

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

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

回答No.1

Tacosan

「できれば C 以外」という理由がよくわからんのだけど, 「C で書かれたものを別の言語にコンバートする」のはダメ?
metric に負のものがなければ Dijkstra の方法でできそうなんだけど, どうやって優先順位キュー (ヒープ) を作りますかねぇ.

お礼

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

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