单源点最长门路.docVIP

单 源 点 最 短 路 径 实 验 一、实验题目： 单源最短路径问题 二、实验目的： 1、掌握贪心算法的基本思想 2、用java程序实现单源最短路径的算法 三、实验环境： Window下的MyEclipse 四、算法描述： 设给定源点为Vs，根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧Vs，Vj；从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定是集合S中值为真的顶点。即只有这条最短路径的最后一条弧才是从集合S中值为真的顶点连接到S集合S中值为假的顶点Vj 。 若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中值为真的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是S中值为假且值最小的顶点。利用公式Dist[j] = Math.min(Dist[j], Dist[u] +Cost[u][j])修改集合S中值为假的节点的路径长度值。 在程序中Cost[][]表示带权邻接矩阵,Dist[]表示源点到顶点的最短路径, v是源点。 五、源程序： package Chapter15; import java.lang.Math; public class Dijkstra { static int n = 7; public static void dijkstra(int v, int[][] Cost, boolean[] s, int[] Dist){ if(v 0 || v n-1) return; for(int i = 0; i n; i++){ s[i] = false; Dist[i] = Cost[v][i]; } s[v] = true; Dist[v] = 0; for(int i = 0; i n; i++){ int temp = Integer.MAX_VALUE; int u = v; for(int j = 0; j n; j++){ if(!s[j] (Dist[j]temp)){ u = j; temp = Dist[j]; } } s[u] = true; for(int j = 0; j n; j++){ if(!s[j] (Cost[u][j] Integer.MAX_VALUE)){ Dist[j] = Math.min(Dist[j], Dist[u] +Cost[u][j]); } } } } public static void main(String[] args) { // TODO Auto-generated method stub boolean s[] =new boolean[n]; int Cost[][] = new int[n][n]; for(int i = 0; i n; i++){ for(int j = 0; j n; j++){ if(i == j){ Cost[i][j] = 0; }else Cost[i][j]=Integer.MAX_VALUE; } Cost[0][1]=20; Cost[0][2]=50; Cost[0][3]=30; Cost[1][2]=25; Cost[1][5]=70; Cost[2][3]=40; Cost[2][4]=25; Cost[2][5]=50; Cost[3][4]=55; Cost[4][5]=10; Cost[4][6]=70; Cost[5][6]=50; } int Dist[] = new int[n]; int v = 0; dijkstra(v,Cost, s, Dist); System.out.println(从0出发到1、2、3、4、5、6的最短路径依次是:); for(int j = 1;j = 6; j++){ System.out.println(Dist[j]); } } } 六、运行结果：