testdijkstra.java

贪心法的算法

package greedy;

public class TestDijkstra {
	
	public static void dijkstra(int v,float[][] a,float[] dist,int[] prev) {
		int n = dist.length - 1;
		if(v < 1 || v > n) {
			return; 
		}
		boolean[] s = new boolean[n+1];
		//初始化
		for(int i = 1;i <= n;i++) {
			dist[i] = a[v][i];
			s[i] = false;
			if(dist[i] == Float.MAX_VALUE) {
				prev[i] = 0;
			}	else {
				prev[i] = v;
			}
		}
			dist[v] = 0;
			s[v] = true;
			for(int j = 1;j < n;j++) {
				float temp = Float.MAX_VALUE;
				int u = v;
				for(int k = 1;k <= n;k++) {
					if((!s[k])&&(dist[k]<temp)) {
						u = k;
						temp = dist[k];
					}
				}
					s[u] = true;
					for(int p = 1;p <= n;p++) {
						if((!s[p])&&(a[u][p] < Float.MAX_VALUE)) {
							float newdist = dist[u] + a[u][p];
							if(newdist < dist[p]) {
								dist[p] = newdist;
								prev[p] = u;
							}
						}
					}
			}
	}
	public static void main(String[] args) {
		int n = 5;
		float[][] c = new float[n+1][n+1];
		float max = Float.MAX_VALUE;
		for(int i = 0;i<=n;i++) {
			for(int j = 0;j<=n;j++) {
				c[i][j] = max;
			}
		}
		
		c[1][2] = 10;
		c[1][4] = 30;
		c[1][5] = 100;
		c[2][3] = 50;
		c[3][5] = 10;
		c[4][3] = 20;
		c[4][5] = 60;
		/*
		for(int i = 0;i<=n;i++) {
			for(int j = 0;j<=n;j++) {
				System.out.println("c["+i+"]["+j+"] = " +c[i][j]);
			}
		}
		*/
		float[] dist = new float[n+1];
		int[] prev = new int[n+1];
		dijkstra(1,c,dist,prev);
		System.out.println("单源最短路径：");
		for(int i = 1;i <= n;i++) {
			System.out.println("prev["+i+"] = "+prev[i]);
		}
	}
}