实验1. 贪心法求解单源最短路径问题
实验内容
本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试）。应用贪心策略求解有向带权图的单源最短路径问题。
实验目的
通过本次实验，掌握算法设计与分析的一般过程，以及每个步骤的基本方法。并应用贪心法求解单源最短路径问题。
环境要求
对于环境没有特别要求。对于算法实现，可以自由选择C, C++, Java，甚至于其他程序设计语言。
Java
实验步骤
步骤1：理解问题，给出问题的描述。
步骤2：算法设计，包括策略与数据结构的选择
步骤3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等；
步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明； 步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；
步骤6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图; 步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。
说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。
实验结果
步骤1：给定一个有向带权图G=（V ，E ），其中每条边的权是一个非负实数。另外，给定V 中的一个顶点，称为源点。现在要计算从源点到所有其他各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和。这个问题通常称为单源最短路径问题。 步骤2：Dijkstra 算法思想，即先求出长度最短的一条路径，再参照它求出长度此短的一条路径，以此类推，直到从源点到其他各个顶点的最短路径全部求出为止
a ：设计合适的数据结构。带权邻接矩阵C 记录结点之间的权值，数组dist 来记录从源点到其它顶点的最短路径长度，数组p 来记录最短路径；
b ：初始化。令集合S={u}，对于集合V-S 中的所有顶点x ，设置dist[x]=C[u][x]；如果顶点i 与源点相邻，设置p[i]=u，否则p[i]=-1；
c ：贪心选择结点。在集合V-S 中依照贪心策略来寻找使得dist[x]具有最小值的顶点t ，t 就是集合V-S 中距离源点u 最近的顶点
d ：更新集合S 和V-S 。将顶点t 加入集合S 中，同时更新集合V-S ；
e ：判断算法是否结束。如果集合V-S 为空，算法结束。否则，转步骤6；
f ：对相关结点做松弛处理。对集合V-S 中的所有与顶点t 相邻的顶点x ，如dist[x]>dist[t]+C[t][x]，则dist[x]=dist[t]+C[t][x]并设置p[x]=t。
步骤3：
import java.util.Scanner;
public class Theshortapproach {
private static int n;//G图中的顶点个数
private static int []distent = null;//最短路径长度
private static int []previous = null;//前驱顶点集合
public static void dijkstra(int v,int[][] a,int[] dist,int[] prev){
//单源最短路径问题的Dijkstra 算法
int n = dist.length-1; //问题的规模，0号元素未使用
if(v n) return; //源不在图中，则返回
boolean[] s = new boolean[n+1];//判断点是否在集合S 中
//初始化
for(int i = 1;i
dist[i] = a[v][i]; //源到点i 的最短特殊路径长度
s[i] = false; //点i 现在不在集合s 中
if(dist[i] == -1)
prev[i] = 0; //若最短路径长度恒为-1表示无通路，则让点i 的前驱点为0 else
prev[i] = v; //有通路则让点i 的前驱指向源
}
dist[v] = 0;
s[v] = true; //源放入集合s 中
for(int i = 1;i
int temp = Integer.MAX_VALUE;
int u = v;
//在剩下的点中除了没有通路的点中找到最容易到达的，并把最容易到达的放入u 中 for(int j = 1;j
if((!s[j])&&(dist[j]
u = j;
temp = dist[u];
}
}
s[u] = true; //u放入s 集合中
for(int j = 1;j
if((!s[j])&&(a[u][j])!= -1){
//源到点j 通过点u 的最短特殊路径长度newdist
int newdist = dist[u] + a[u][j];
if(newdist
prev[j] = u; //点j 的前驱指向点u
}
}
}
//System.out.println("从1出发到2、3、4、5的最短路径依次为:");
for(int k = 2;k
System.out.print(dist[k]+" ");
}
System.out.println(dist[n]);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int v = 1;
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
n = Integer.parseInt(line);
distent=new int[n+1];
previous=new int[n+1];
int[][] a = new int[n + 1][n + 1];
for(int i=1;i
line=sc.nextLine();
String [] str=line.split(" ");
for(int j=1;j
a[i][j]=Integer.parseInt(str[j - 1]);
}
}
dijkstra(v,a,distent,previous);
int x = previous[5];
int y = previous[x];
int z = previous[y];
//System.out.println("从1到5最短路径经过的点为：");
System.out.println(z+" "+y+" "+x+" "+"5");
}
}
步骤5
算法的时间复杂度为O （n 2）, 算法的空间复杂性为O (n).
步骤6
Dijkstra 算法的正确性证明。
贪心选择性质
Dijkstra 算法是应用贪心法设计策略的又一个典型例子。它所做的贪心选择是从集合V-S 中选择具有最短路径的顶点t, 从而确定从源点u 到t 的最短路径长度dist[t]，这种贪心选择为什么能得到最优解呢？换句话说，为什么从源点到t 没有更短的其他路径呢？
事实上，假设存在一条从源点u 到t 且长度比dist[t]更短的路，设这条路径初次走出S 之外到达的顶点为x 属于V-S ，然后徘徊于S 内外若干次，最后离开S 到达t. 在这条路径上，分别记d(u,x),d(x,t)和d(u,t)为源点u 到顶点x, 顶点x 到顶点t 和源点u 到顶点t 的路径长度，那么，依据假设容易得出;
dist[x]
d(u,x)+d(x,t)=d(u,t)
利用边权的非负性，可知d(x,t)>=0,从而推得dist[x]
实验总结
这次实验是贪心法求单源最短路径问题，即应用贪心策略求解有向带权图的单源最短路径问题。通过这次实验，我对贪心算法有了更进一步的认识，何时用贪心算法，怎样用贪心算法有了更进一步的了解，对于有向带权图中，最短路径的求法也更熟悉，Dijkstra 算法满足贪心选择性质和最优子结构性质，在刚开始写代码时，遇到问题也很多，在舍友帮忙调试下逐渐解决。
实验1. 贪心法求解单源最短路径问题
实验内容
本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试）。应用贪心策略求解有向带权图的单源最短路径问题。
实验目的
通过本次实验，掌握算法设计与分析的一般过程，以及每个步骤的基本方法。并应用贪心法求解单源最短路径问题。
环境要求
对于环境没有特别要求。对于算法实现，可以自由选择C, C++, Java，甚至于其他程序设计语言。
Java
实验步骤
步骤1：理解问题，给出问题的描述。
步骤2：算法设计，包括策略与数据结构的选择
步骤3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等；
步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明； 步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；
步骤6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图; 步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。
说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。
实验结果
步骤1：给定一个有向带权图G=（V ，E ），其中每条边的权是一个非负实数。另外，给定V 中的一个顶点，称为源点。现在要计算从源点到所有其他各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和。这个问题通常称为单源最短路径问题。 步骤2：Dijkstra 算法思想，即先求出长度最短的一条路径，再参照它求出长度此短的一条路径，以此类推，直到从源点到其他各个顶点的最短路径全部求出为止
a ：设计合适的数据结构。带权邻接矩阵C 记录结点之间的权值，数组dist 来记录从源点到其它顶点的最短路径长度，数组p 来记录最短路径；
b ：初始化。令集合S={u}，对于集合V-S 中的所有顶点x ，设置dist[x]=C[u][x]；如果顶点i 与源点相邻，设置p[i]=u，否则p[i]=-1；
c ：贪心选择结点。在集合V-S 中依照贪心策略来寻找使得dist[x]具有最小值的顶点t ，t 就是集合V-S 中距离源点u 最近的顶点
d ：更新集合S 和V-S 。将顶点t 加入集合S 中，同时更新集合V-S ；
e ：判断算法是否结束。如果集合V-S 为空，算法结束。否则，转步骤6；
f ：对相关结点做松弛处理。对集合V-S 中的所有与顶点t 相邻的顶点x ，如dist[x]>dist[t]+C[t][x]，则dist[x]=dist[t]+C[t][x]并设置p[x]=t。
步骤3：
import java.util.Scanner;
public class Theshortapproach {
private static int n;//G图中的顶点个数
private static int []distent = null;//最短路径长度
private static int []previous = null;//前驱顶点集合
public static void dijkstra(int v,int[][] a,int[] dist,int[] prev){
//单源最短路径问题的Dijkstra 算法
int n = dist.length-1; //问题的规模，0号元素未使用
if(v n) return; //源不在图中，则返回
boolean[] s = new boolean[n+1];//判断点是否在集合S 中
//初始化
for(int i = 1;i
dist[i] = a[v][i]; //源到点i 的最短特殊路径长度
s[i] = false; //点i 现在不在集合s 中
if(dist[i] == -1)
prev[i] = 0; //若最短路径长度恒为-1表示无通路，则让点i 的前驱点为0 else
prev[i] = v; //有通路则让点i 的前驱指向源
}
dist[v] = 0;
s[v] = true; //源放入集合s 中
for(int i = 1;i
int temp = Integer.MAX_VALUE;
int u = v;
//在剩下的点中除了没有通路的点中找到最容易到达的，并把最容易到达的放入u 中 for(int j = 1;j
if((!s[j])&&(dist[j]
u = j;
temp = dist[u];
}
}
s[u] = true; //u放入s 集合中
for(int j = 1;j
if((!s[j])&&(a[u][j])!= -1){
//源到点j 通过点u 的最短特殊路径长度newdist
int newdist = dist[u] + a[u][j];
if(newdist
prev[j] = u; //点j 的前驱指向点u
}
}
}
//System.out.println("从1出发到2、3、4、5的最短路径依次为:");
for(int k = 2;k
System.out.print(dist[k]+" ");
}
System.out.println(dist[n]);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int v = 1;
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
n = Integer.parseInt(line);
distent=new int[n+1];
previous=new int[n+1];
int[][] a = new int[n + 1][n + 1];
for(int i=1;i
line=sc.nextLine();
String [] str=line.split(" ");
for(int j=1;j
a[i][j]=Integer.parseInt(str[j - 1]);
}
}
dijkstra(v,a,distent,previous);
int x = previous[5];
int y = previous[x];
int z = previous[y];
//System.out.println("从1到5最短路径经过的点为：");
System.out.println(z+" "+y+" "+x+" "+"5");
}
}
步骤5
算法的时间复杂度为O （n 2）, 算法的空间复杂性为O (n).
步骤6
Dijkstra 算法的正确性证明。
贪心选择性质
Dijkstra 算法是应用贪心法设计策略的又一个典型例子。它所做的贪心选择是从集合V-S 中选择具有最短路径的顶点t, 从而确定从源点u 到t 的最短路径长度dist[t]，这种贪心选择为什么能得到最优解呢？换句话说，为什么从源点到t 没有更短的其他路径呢？
事实上，假设存在一条从源点u 到t 且长度比dist[t]更短的路，设这条路径初次走出S 之外到达的顶点为x 属于V-S ，然后徘徊于S 内外若干次，最后离开S 到达t. 在这条路径上，分别记d(u,x),d(x,t)和d(u,t)为源点u 到顶点x, 顶点x 到顶点t 和源点u 到顶点t 的路径长度，那么，依据假设容易得出;
dist[x]
d(u,x)+d(x,t)=d(u,t)
利用边权的非负性，可知d(x,t)>=0,从而推得dist[x]
实验总结
这次实验是贪心法求单源最短路径问题，即应用贪心策略求解有向带权图的单源最短路径问题。通过这次实验，我对贪心算法有了更进一步的认识，何时用贪心算法，怎样用贪心算法有了更进一步的了解，对于有向带权图中，最短路径的求法也更熟悉，Dijkstra 算法满足贪心选择性质和最优子结构性质，在刚开始写代码时，遇到问题也很多，在舍友帮忙调试下逐渐解决。