1、单源最短路径问题的问题提出是，计算带权有向图G =(V, E)中一个点（源点）到其余各顶点的最短路径长度，如下图所示。设源点为顶点1，采用Dijkstra算法求下图中源V0为到其余各顶点的最短路径。
1）将算法编程实现, 并将程序与运算结果截屏填写入实验结果。
package test;public class twelve {static float[][] a = {{0,0,0,0,0,0,0},{0,0,3,4,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE},{0,Float.MAX_VALUE,0,1,9,4,Float.MAX_VALUE},{0,Float.MAX_VALUE,Float.MAX_VALUE,0,5,13,Float.MAX_VALUE},{0,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,0,Float.MAX_VALUE,8},{0,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,12,0,10},{0,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,0}};//static float[][] a = {//{0,0,0,0,0,0},//{0,0,10,Float.MAX_VALUE,30,100},//{0,Float.MAX_VALUE,0,50,Float.MAX_VALUE,Float.MAX_VALUE},//{0,Float.MAX_VALUE,Float.MAX_VALUE,0,Float.MAX_VALUE,10},//{0,Float.MAX_VALUE,Float.MAX_VALUE,20,0,60},//{0,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,Float.MAX_VALUE,0}//};static int n = a.length-1;static float[] dist = new float[n+1];static int[] prev = new int[n+1];public static void main(String[] args) {dijkstra(1,a,dist,prev);show(dist);show(prev);}public static void show(float[] a){for(int i = 2;i < a.length;i++){System.out.print(a[i]+" ");}System.out.println();}public static void show(int[] a){for(int i = 2;i < a.length;i++){System.out.print(a[i]+" ");}System.out.println();}public static void dijkstra(int v/*源点*/, float[][] a/*图G的邻接矩阵*/, float[] dist/*最短特殊路径长度*/, int[] prev/*从源点到顶点u到最短路径中顶点u的前一个顶点*/){if(v<1||v>n) return;//参数不合规范则直接结束boolean[] s = new boolean[n+1];//标记是否加入到集合Sfor(int i = 1;i <= n;i++)//初始化{dist[i] = a[v][i];s[i] = false;//标记为未加入到集合Sif(dist[i] == Float.MAX_VALUE) prev[i] = 0;//如果距离为无穷大则标记为无通路到达else prev[i] = v;//否则标记前驱节点}dist[v] = 0;s[v] = true;//顶点距离到目前顶点距离为0，并加入到集合Sfor(int i = 1;i < n;i++)//选择路径长最短的点加入到集合S中{float temp = Float.MAX_VALUE;//无穷大int u = v;//for(int j = 1;j <= n;j++)if(!s[j]&&(dist[j]<temp))//如果未加入到集合S且距离为目前dist中最小值{u = j;temp = dist[j];}s[u] = true;//加入到集合S中for(int j = 1;j <= n;j++)if(!s[j]&&(a[u][j]<Float.MAX_VALUE)){float newdist = dist[u] + a[u][j];if(newdist < dist[j]){dist[j] = newdist;//将最短路径长记录到dist表prev[j] = u;}}}}}
运行结果截图：
2）分析Dijkstra算法的时间复杂性。
由代码可知，两层嵌套的for循环，时间复杂度为O(n²)。
2、设G=(V,E)是连通带权图，如下图所示：
使用Prim算法建立G的最小生成树：
1）将算法编程实现, 将程序与运算结果截屏填入实验结果。
package evelen_24;public class twelve {//static float[][] c = {//{0,0,0,0,0,0,0},//{0,0,6,1,5,Float.MAX_VALUE,Float.MAX_VALUE},//{0,6,0,5,Float.MAX_VALUE,3,Float.MAX_VALUE},//{0,1,5,0,5,6,4},//{0,5,Float.MAX_VALUE,5,0,Float.MAX_VALUE,2},//{0,Float.MAX_VALUE,3,6,Float.MAX_VALUE,0,6},//{0,Float.MAX_VALUE,Float.MAX_VALUE,4,2,6,0}//};static float[][] c = {{0,0,0,0,0,0,0},{0,0,34,Float.MAX_VALUE,Float.MAX_VALUE,12,Float.MAX_VALUE},{0,34,0,46,Float.MAX_VALUE,Float.MAX_VALUE,19},{0,Float.MAX_VALUE,46,0,17,Float.MAX_VALUE,25},{0,Float.MAX_VALUE,Float.MAX_VALUE,17,0,38,25},{0,12,Float.MAX_VALUE,Float.MAX_VALUE,38,0,26},{0,Float.MAX_VALUE,19,25,25,26,0}};static int n = c.length-1;public static void main(String[] args) {prim(n, c);}public static void prim(int n,float[][] c/*边的权，邻接矩阵*/){float[] lowcost = new float[n+1];//记录顶点集合V-S中的顶点j到顶点集合S的距离int[] closest = new int[n+1];//记录集合S中离顶点j最近的顶点boolean[] s = new boolean[n+1];//标记是否加入到集合S中s[1] = true;for(int i = 2;i <= n;i++)//初始化{lowcost[i] = c[1][i];closest[i] = 1;s[i] = false;}for(int i = 1;i <= n;i++)//更新表中值{float min = Float.MAX_VALUE;//无穷大int j = 1;for(int k = 2;k <= n;k++)if((lowcost[k] < min)&& (!s[k])){min = lowcost[k];j = k;}//System.out.println(j+" , "+closest[j]);s[j] = true;for(int k = 2;k <= n;k++)if((c[j][k] < lowcost[k])&&(!s[k]))//未加入到集合S中且距离更短{lowcost[k] = c[j][k];closest[k] = j;//前驱结点更新}}show(lowcost);show(closest);}public static void show(float[] a){for(int i = 2;i < a.length;i++){System.out.print(a[i]+" ");}System.out.println();}public static void show(int[] a){for(int i = 2;i < a.length;i++){System.out.print(a[i]+" ");}System.out.println();}}
运行结果截图：
2）分析算法的时间复杂性。
由代码可知，两层嵌套的for循环，时间复杂度为O(n²)
来自《算法基础与实验》
