public class Edge {
	Point start;
	Point end;
	double length;
public Edge(Point start, Point end, int length) {
	this.start = start;
	this.end = end;
	this.length = length;
}
}
public class Path {

	Point source;
	Point end;
	List<Point> points;
	double length;
	
	public Path(Point source, Point end, List<Point> points,
			double length) {
		this.source = source;
		this.end = end;
		this.points = points;
		this.length = length;
	}
}
public class Point {

	
	String name;
	//经度
	double x = 0;
	//纬度
	double y = 0;
	int lu = 0;
	//是否为交叉点
	boolean isCross;
	//是否为红点，如果源点到该点的最短路径已经求出，该点变为红点
	boolean isRed;
	//是否为源点
	boolean isSource;
	
	public Point(String name) {
		this.name = name;
	}

	public void setRed(boolean b) {
		isRed = b;
	}

	public void setSource(boolean b) {
		isSource = b;
	}
}

package abc.Dijkstra.pack;

import java.util.ArrayList;
import java.util.List;

public class Client {
	public static void main(String[] args) {
		long initBegin = System.currentTimeMillis();
		Point A = new Point("A");
		Point B = new Point("B");
		Point C = new Point("C");
		Point D = new Point("D");
		Point E = new Point("E");
		Point F = new Point("F");
		Point G = new Point("G");
		Point H = new Point("H");
		Point I = new Point("I");
		Point J = new Point("J");
		Point K = new Point("K");
		Point L = new Point("L");
		
		A.setRed(true);
		A.setSource(true);
		
		List<Point> points = new ArrayList<Point>();
		points.add(B);
		points.add(A);
		points.add(C);
		points.add(D);
		points.add(E);
		points.add(F);
		points.add(G);
		points.add(H);
		points.add(I);
		points.add(J);
		points.add(K);

//		for (int i = 0; i < 10000; i++) {
//			Point point = new Point(""+i);
//			points.add(point);
//		}
		
		List<Edge> edges = new ArrayList<Edge>();
		edges.add(new Edge(A,B,19));
		edges.add(new Edge(B,C,25));
		edges.add(new Edge(B,D,8));
		edges.add(new Edge(C,E,10));
		edges.add(new Edge(D,A,20));
		edges.add(new Edge(D,C,4));
		edges.add(new Edge(D,E,12));
		
		edges.add(new Edge(A,E,13));
		edges.add(new Edge(B,F,25));
		edges.add(new Edge(C,F,2));
		edges.add(new Edge(D,F,10));
		
		edges.add(new Edge(F,I,20));
		edges.add(new Edge(F,K,16));
		edges.add(new Edge(C,G,5));
		edges.add(new Edge(G,I,10));
		edges.add(new Edge(G,K,1));
		edges.add(new Edge(G,H,7));
		edges.add(new Edge(H,J,20));
		edges.add(new Edge(H,K,45));
		edges.add(new Edge(I,J,4));
		edges.add(new Edge(J,K,3));

//		for (int i = 0; i < points.size(); i++) {
//			for (int j = i; j < points.size()-i+1; j++) {
//				if (j<points.size()&&(j==i+1||j==10*i+1)) {
//					edges.add(new Edge(points.get(i),points.get(j),100*Math.random()));
//				}
//			}
//		}

		System.out.println(edges.size());
		long initEnd = System.currentTimeMillis();
		System.out.println("init time:"+(initEnd-initBegin)/60);
		
		long computeBegin = System.currentTimeMillis();
		Dijkstra dijkstra = new Dijkstra();
		dijkstra.setPoints(points);
		dijkstra.setEdges(edges);
		dijkstra.dijkstra(A);
		dijkstra.display();
		long computeEnd = System.currentTimeMillis();
		System.out.println("compute time:"+(computeEnd-computeBegin)/1000);
	}
}

package abc.Dijkstra.pack;

import java.util.ArrayList;
import java.util.List;

public class Dijkstra {
	private List<Point> points;
	private List<Edge> edges = new ArrayList<Edge>();;
	private List<Path> paths = new ArrayList<Path>();
	//当前变为红点的点
	private Point currentPoint;
	private final double INFINITY = 999999;
	//源点到当前红点的长度
	private double startToCurrent;
	
	/**
	 * 初始化源点到其他各点的路径，即Path
	 */
	public void init(){
		Point source = null;
		for (Point point : points) {
			if (point.isSource) {
				source = point;
			}
		}
		//设置路径的终点
		for (Point point : points) {
			List<Point> redPoints = new ArrayList<Point>();
			redPoints.add(source);
			Path path = new Path(source, point, redPoints, INFINITY);
			paths.add(path);
		}
		//设置路径的长度，当存在这样的边：起始，结束点分别和路径的源点，终点相同
		for (Path path : paths) {
			for (Edge edge: edges) {
				if (path.source.name.equals(edge.start.name) && path.end.name.equals(edge.end.name)) {
					path.length = edge.length;
				}
			}
		}
	}
	
	public void dijkstra(){
		dijkstra(null);
	}
	
	public void dijkstra(Point end){
		init();
		for (int i = 0; i < paths.size(); i++) {
			int indexMin = getMin();
			double minDist = paths.get(indexMin).length;
			if (minDist==INFINITY) {
				System.out.println("有无法到达的顶点");
			}else if(i!=paths.size()-1){
				//获取当前循环已经求出最短路径的点
	            currentPoint = paths.get(indexMin).end;
	            paths.get(indexMin).points.add(currentPoint);
	            startToCurrent = minDist;
	        }
			//将当前点设为红点
			for (Point point : points) {
				if (point.name.equals(currentPoint.name)) {
					point.isRed = true;
					if (end!=null && end.name.equals(point.name)) {
						return;
					}
				}
			}
			resetPaths();
		}
	}

	/**
	 * 在路径集合中获取长度最小的索引值
	 * @return
	 */
	private int getMin() {
		double minDist = INFINITY;
        int indexMin = 0;
		for (int i = 0; i < paths.size(); i++) {
			Path path = paths.get(i);
			if (!path.end.isRed && path.length < minDist) {
				minDist = path.length;
				indexMin = i;
			}
		}
		return indexMin;
	}

	/**
	 * 在当前红点发生变化后，源点到其他点的路径也相应变化，通过当前红点，
	 * 之前不可到的点有可能变为可到达，
	 * 之前可到达的点路径长度会发生改变
	 * 所以要重置其他路径的长度
	 */
	private void resetPaths() {
		for (Path path : paths) {
			if (path.end.isRed) {
				continue;
			}
			for (Edge edge: edges) {
				if (edge.start.name.equals(currentPoint.name) && edge.end.name.equals(path.end.name)) {
					double currentToFringe = edge.length;
					double startToFringe = startToCurrent + currentToFringe;
					double pathLength = path.length;
					if(startToFringe<pathLength) {
	                  path.points.add(currentPoint);
	                  path.length = startToFringe;
					}
				}
			}
		}
		
	}
	
	public void display(){
		for (Path path : paths) {
			System.out.print(path.source.name +"-->"+ path.end.name+":");
			for (Point point : path.points) {
				System.out.print(point.name+"  ");
			}
			System.out.print(path.length);
			System.out.println();
		}
	}

	public void setPoints(List<Point> points2) {
		this.points = points2;
	}

	public void setEdges(List<Edge> edges2) {
		this.edges = edges2;
	}


}	

read file:
// Read a file as a single string:
public static String read(String fileName) {
  StringBuilder sb = new StringBuilder();
  try {
    bufferedReader in = new BufferReader(new FileReader(new File(fileName).getAbsoluteFile()));
    try {
      String s;
      while((s = in.readLine()) != null) {
        sb.append(s);
        sb.append("\n");
      }
    } finally {
      in.close();
    }
  } catch(IOException e) {
    throw new RuntimeException(e);
  }
  return sb.toString();
}
    

write file:
// Write a single file in one method call:
public static void write(String fileName, String text) {
  try {
    PrintWrite out = new PrintWriter(new File(fileName).getAbsoluteFile());
    try {
      out.print(text);
    } finally {
      out.close();
    }
  } catch(IOException e) {
    throw new RuntimeException(e);
  }
}

package com.javapatterns.command;

public class Client
{
    public static void main(String[] args)
    {
        Receiver receiver = new Receiver();
        Command command = new ConcreteCommand(receiver);
    	Invoker invoker = new Invoker( command );

        invoker.action();
    }

    /** @link dependency */
    /*#Receiver lnkReceiver;*/

    /** @link dependency */
    /*#Invoker lnkInvoker;*/
}