dijkstra.d

import std.stdio;

/* 要素がすべて無限大である、num_v * num_v の2重配列 */
pure real[][] make_cost(int num_v)
{
  real[][] cost;

  cost.length = num_v+1;
  for(int i;i<=num_v;i++){
    cost[i].length = num_v+1;
    for(int j;j<=num_v;j++){
      cost[i][j] = real.infinity;
    }
  }
  return cost;
}

/* dijkstra法 */
real dijkstra(int[][] edge, int numv, int start)
{
  real[][] cost = make_cost(numv);
  int[] used;
  real[] d;

  foreach(int i, int[] e; edge){
    cost[e[0]][e[1]] = e[2];
  }

  used.length = numv+1;
  d.length = numv+1;

  for(int i;i<=numv;i++){
    used[i] = 0;
    d[i] = real.infinity;
  }

  d[start] = 0;

  while(true){
    uint tmp = d.length;
    for(int i;i<=numv;i++){
      if((used[i]==0) && ((tmp == d.length) || (d[i] < d[tmp]))){
        tmp = i;
      }
    }
    if(tmp == d.length){ break;}

    used[tmp] = 1;

    for(int i;i<=numv;i++){
      d[i] = d[i] < d[tmp]+cost[tmp][i] ? d[i] : d[tmp]+cost[tmp][i];
    }
    writeln(d);
  }
  return d[numv];
}

void main(char[][] args){
  int[][] edge = [[0,1,2],  [0,2,5], [1,2,4],  [1,3,6], 
                  [1,4,10], [2,3,2], [3,5,1],  [4,5,3],
                  [4,6,5],  [5,6,9], [1,0,2],  [2,0,5],
                  [2,1,4],  [3,1,6], [4,1,10], [3,2,2],
                  [5,3,1],  [5,4,3], [6,4,5],  [6,5,9]];

  writeln(dijkstra(edge, 6, 0));
}