shortestpath.java

java 实现的一些算法： 赛选法求素数

package daniel.graph_theory;

import java.util.Scanner;

/**
 * 
 * @author Daniel Cao
 * 
 */
public class ShortestPath {
	public static final int MAX_SIZE = 8;
	public static final int MAX_NUM = 9999;

	static int dis[][] = new int[MAX_SIZE][MAX_SIZE];
	// p[i,j]表示i到j的最短路径上j的前驱结点
	static int p[][] = new int[MAX_SIZE][MAX_SIZE];

	// 用dijkstra算法时： 原点到目标点的最短路径。
	static int v[] = new int[MAX_SIZE];

	public static void floyd() {
		for (int i = 0; i < MAX_SIZE; i++) {
			for (int j = 0; j < MAX_SIZE; j++) {
				if (dis[i][j] != MAX_NUM) {
					p[i][j] = i;
				}
			}
		}

		for (int k = 0; k < MAX_SIZE; k++) {
			for (int i = 0; i < MAX_SIZE; i++) {
				for (int j = 0; j < MAX_SIZE; j++) {
					if (dis[i][k] + dis[k][j] < dis[i][j]) {
						dis[i][j] = dis[i][k] + dis[k][j];
						p[i][j] = p[k][j];
					}
				}
			}
		}

	}

	public static void dijkstra(int s) {
		boolean[] b = new boolean[MAX_SIZE];
		for (int i = 0; i < v.length; i++) {
			v[i] = dis[s][i];
			p[s][i] = s;
		}
		b[s] = true;
		for (int i = 1; i < v.length; i++) {
			int min = MAX_NUM;
			int point = 0;
			for (int j = 0; j < v.length; j++) {
				if (!b[j] && v[j] < min) {
					min = v[j];
					point = j;
				}
			}
			b[point] = true;
			for (int j = 0; j < v.length; j++) {
				if (!b[j]&&v[j] > v[point] + dis[point][j]) {
					v[j] = v[point] + dis[point][j];
					p[s][j] = point;
				}
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		init();
//		floyd();
		Scanner scan = new Scanner(System.in);
		int i = scan.nextInt();
		dijkstra(i);
		while (scan.hasNext()) {
			int j = scan.nextInt();
			printShortPath(i,j,v[j]);
		}
	}

	private static void printShortPath(int i, int j,int lenth) {
		System.out.println("dis: " + lenth);
		int k = j;
		int x = 0;
		while (i != k) {
			System.out.print(k + "<-");
			k = p[i][k];
			x ++;
			if(x >10)break;
		}
		System.out.println(i);
	}

	public static void init() {
		for (int i = 0; i < MAX_SIZE; i++) {
			for (int j = 0; j < MAX_SIZE; j++) {
				if (i != j) {
					dis[i][j] = MAX_NUM;
				}
			}
		}
		dis[0][1] = dis[1][0] = 3;
		dis[1][2] = dis[2][1] = 2;
		dis[1][3] = dis[3][1] = 3;
		dis[2][6] = dis[6][2] = 7;
		dis[3][4] = dis[4][3] = 4;
		dis[3][5] = dis[5][3] = 2;
		dis[3][6] = dis[6][3] = 2;
		dis[3][7] = dis[7][3] = 10;
		dis[5][7] = dis[7][5] = 5;
	}
}