perlでダイクストラ法

なんとなくダイクストラ法を使う機会がありそうなので、勉強がてらに。
ダイクストラ法は、2点間の最短距離を求めるアルゴリズムです。
カーナビとかにも使われているらしいです。

以下、さんぷるこーど。

#!/usr/bin/perl

use strict;
use Dumpvalue;

my @nodes = (
  {
    id       => 0,
    point    => [0,0],
    edges    => {1=>5,3=>6,4=>9},
    distance => 0,
    done     => 1,
    from     => undef,
  },
  {
    id       => 1,
    point    => [2,0],
    edges    => {0=>5,2=>5,3=>2,4=>2,5=>6},
    distance => 0,
    done     => undef,
    from     => undef,
  },
  {
    id       => 2,
    point    => [4,0],
    edges    => {1=>5,4=>1,5=>8},
    distance => 0,
    done     => undef,
    from     => undef,
  },
  {
    id       => 3,
    point    => [0,2],
    edges    => {0=>6,1=>2,4=>8},
    distance => 0,
    done     => undef,
    from     => undef,
  },
  {
    id       => 4,
    point    => [2,2],
    edges    => {0=>9,1=>2,2=>1,3=>8,5=>10},
    distance => 0,
    done     => undef,
    from     => undef,
  },
  {
    id       => 5,
    point    => [2,4],
    edges    => {1=>6,2=>8,4=>10},
    distance => 0,
    done     => undef,
    from     => undef,
  },
);

# 最短経路リスト
my $roots = {};

# スタートノード
my $done_node = $nodes[0];

while (1) {
  my $next_node = undef;
  my $distance = 0;
  
  # 次に伸びているノードの中で最小のものを調査
  while (my($edge,$cost) = each(%{$done_node->{edges}})) {
    # 既に通った道か？
    if ($nodes[$edge]->{done}) {
      next;
    }
    
    # 距離計算
    if (!$roots->{$edge} || $done_node->{distance} + $cost < $roots->{$edge}) {
      $nodes[$edge]->{distance} = $done_node->{distance} + $cost;
      $nodes[$edge]->{from}     = $done_node->{id};
      
      # 最短経路登録
      $roots->{$edge} = $nodes[$edge]->{distance};
    }
    
    # 比較
    if (!$next_node || $nodes[$edge]->{distance} < $next_node->{distance}) {
      $next_node = $nodes[$edge];
    }
  }
  
  # 次のノードが決まらなかった場合
  if (!$next_node) {
    last;
  }
  
  # 既に通った道として登録
  $next_node->{done} = 1;
  
  $done_node = $next_node;
}

# dump data
Dumpvalue->new->dumpValue(\$roots);

※追記
ダイクストラ法は、色々ある道の中で最短の経路を見出すもので、
全部の道を通っていく最短のルートを計算するのはワーシャルフロイド法ってヤツで計算するみたい。
若干勘違いしてたのでメモ。