kadai2

import java.util.*;
class Dijkstra extends Graph{

int slowDijkstra(int start) {
 double D = new double[nodes.size()]; //頂点ごとへの最短距離//
 int Search = new int [nodes.size()];
 int
tree = new int [nodes.size()];
 int remain = nodes.size() - 1; // ループ回数 //
 for (int i = 0; i < nodes.size() ;i++) {
 D[i] = Double.MAX_VALUE; Search[i] = 1; tree[i] = -1;
 }
  D[start] = 0; Search[start] = 0; tree[start] = start;
 while(remain != 0) {
 int u = 0;  // u:node 軽い//
 double min =  Double.MAX_VALUE;
 for (int j = 0; j < D.length; j++) {  
 if ( min > D[j] && Search[j] == 1)  {
 u = j; min = D[j]; 
  }
 }
 Search[u] = 0;
 for(int k = 0; k < nodes.get(u).Num(); k++) {
 if *1;
 tree[list.get(nodes.get(u).Pointer() + k).To()] = u;
   }
  }
   remain--;
   }
  return tree;
  }
int getShortestPath(int start, int end) {
 ArrayList<Integer> path = new ArrayList<Integer>();
 int tree
= slowDijkstra(start);
 path.add(end);
 while( end != start) {
 path.add(tree[end]);
 end = tree[end];
 }
 int Path = new int [path.size()];
 for (int l = 0; l < path.size(); l++) {
 Path[l] = path.get( (path.size()-1) - l);
 }
 return Path;
 }
}

class DijkstraTester {
public static void main (String args){
 int Tree;
 Dijkstra d = new Dijkstra();
 d.LoadGraph("graph001.txt");
 Tree = d.slowDijkstra(2);
 System.out.print(Tree[0]);
 for (int m = 1; m < Tree.length; m++)
 System.out.print("," + Tree[m]);
 System.out.println();
 int Path = d.getShortestPath(0,4);
 System.out.print(Path[0]);
 for (int n = 1; n < Path.length; n++)
 System.out.print(" " + Path[n]);
  }
 }
 
 
 
 
 
 
 
 
 
 
 
 
import java.util.*;
import java.io.*;
public class Graph {
 int num = 0;
  ArrayList<Edge> list = new ArrayList<Edge>();  //隣接ノード、重さ//
  ArrayList<Node> nodes = new ArrayList<Node>();  //ノード番号、隣接数、先頭オフセット//
 class Edge {
  private int to; private double weight;
  Edge(int to, double weight) {this.to = to; this.weight = weight;}
  int To() { return to;}
  double Weight() { return weight;}
 }
 class Node {
  int id; int Num; int pointer;
  Node (int id,int Num, int pointer) {this.id = id; this.Num = Num; this.pointer = pointer;}
  int Num() {return this.Num;}
  int Id(){ return this.id;}
  int Pointer() { return this.pointer;}
  }

 void LoadGraph(String filename){
 try{
  Scanner scan = new Scanner(new File(filename));
  int pointer = 0;
 while(true){
 if( !scan.hasNextLine()) {
   break;
 }
 String line = scan.nextLine();
 String s = line.split(":",0);
 if (s.length != 1){
 String t = s[1].split(",",0);
 for (int i = 0; i < t.length; i++) {
 String[] u = t[i].split("@",2);
 Edge e = new Edge(Integer.parseInt(u[0]), Double.parseDouble(u[1]));
 list.add(e);
  }
 
 Node n = new Node(Integer.parseInt(s[0]), t.length, pointer);
 nodes.add(n);
 num ++; //ノード数//
 pointer = pointer + t.length ;
  }
 else {
  Node n = new Node(Integer.parseInt(s[0]),0 , pointer);
 nodes.add(n);
 num ++; //ノード数//
 }
 }
 } catch (java.io.FileNotFoundException e){
  System.out.println(e);
  System.exit(0);
  }
 }

 void printGraph(){
 for (int j = 0; j < num ; j++) {
 System.out.print(nodes.get(j).Id() + ":");
 for (int k = 0; k < nodes.get(j).Num(); k++) {
 System.out.print(list.get(nodes.get(j).Pointer() + k).To() + "@" + list.get(nodes.get(j).Pointer()+k).Weight());
 if (k < nodes.get(j).Num() - 1)
 System.out.print(",");
   }
 System.out.println();
  }
 }
}
 
 

*1:D[list.get(nodes.get(u).Pointer() + k).To()] > ( D[u] + list.get(nodes.get(u).Pointer() + k).Weight()))) {
 D[list.get(nodes.get(u).Pointer() + k).To()] =
   ( D[u] + list.get(nodes.get(u).Pointer() + k).Weight(