#!/usr/bin/env ruby
#
# dijkstra's algorithm based on the pseudo code in the wikipedia
# http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
#
require 'optparse'

source = nil	# source of spanning-tree

OptionParser.new {|opt|
  opt.on('-s VAL') {|v| source = v}
  opt.parse!(ARGV)
}

INFINITY = 0x7fffffff	# constant to represent a large number

# read topology file and initialize nodes and edges
# each line of topology file should be "node1 (-|->) node2 weight_val"
nodes = Array.new	# all nodes in graph
edges = Hash.new	# all edges in graph
ARGF.each_line do |line|
  s, op, t, w = line.split
  next if line[0] == ?# || w == nil
  unless op == "-" || op == "->"
    raise ArgumentError, "edge_type should be either '-' or '->'"
  end
  weight = w.to_i

  nodes << s unless nodes.include?(s) # add s to nodes
  nodes << t unless nodes.include?(t) # add t to nodes
  # add this to edges
  if (edges.has_key?(s))
    edges[s][t] = weight
  else
    edges[s] = {t=>weight}
  end
  # if this edge is undirected, add the reverse directed edge
  if (op == "-")
    if (edges.has_key?(t))
      edges[t][s] = weight
    else
      edges[t] = {s=>weight}
    end
  end
end

# sanity check
if source == nil
  raise ArgumentError, "specify source_node by '-s source'"
end
unless nodes.include?(source)
  raise ArgumentError, "source_node(#{source}) is not in the graph"
end

# create and initialize 2 hashes: distance and previous
dist = Hash.new		# distance for destination
prev = Hash.new		# previous node in the best path
nodes.each do |i|
  dist[i] = INFINITY	# Unknown distance function from source to v
  prev[i] = -1		# Previous node in best path from source
end

# run the dijkstra algorithm
dist[source] = 0	# Distance from source to source
while (nodes.length > 0)
  # u := vertex in Q with smallest dist[]
  u = nil
  nodes.each do |v|
    if (!u) || (dist[v] < dist[u])
      u = v
    end
  end
  if (dist[u] == INFINITY)
    break	# all remaining vertices are inaccessible from source
  end
  nodes = nodes - [u]		# remove u from Q
  # update dist[] of u's neighbors
  edges[u].keys.each do |v|
    alt = dist[u] + edges[u][v]
    if (alt < dist[v])
      dist[v] = alt
      prev[v]  = u
    end
  end
end

# print the shortest-path spanning-tree
dist.sort.each do |v, d|
  print "#{v}: "	# destination node
  if d != INFINITY
    print "(#{d}) "	# distance
    # construct path from dest to source
    i = v
    path = "#{i}"
    while prev[i] != -1 do
      path.insert(0, "#{prev[i]} ")	# prepend previous node
      i = prev[i]
    end
    puts "#{path}"	# print path from source to dest
  else
    puts "unreachable"
  end
end