贪心算法求单源最短路径（迪杰斯特拉算法）_单源最短路径贪心算法

目录：

一、单源最短路径问题描述

二、Dijkstra算法及其思想

1.Dijkstra算法描述

2.Dijkstra算法思想

三、具体案例分析

四、具体代码实现

五、Dijkstra算法与Prim算法的区别

---

一、单源最短路径问题描述

①给定带权有向图G =(V,E)。其中V是图中所有顶点的集合，E是图中所有边的集合，每条边的权值是非负实数。

②给定V中的一个顶点，称为源。

③计算从源到所有其它各顶点的最短路长度。

而Dijkstra算法正是最具代表性的解单源最短路径问题的贪心算法。

二、Dijkstra算法及其思想

1.Dijkstra算法描述

①设置顶点集合U，U表示已选择的节点，所以初始化的U中仅包含源结点。

②设置一张表，表中记录源结点通过U内结点到达U外V内结点的路径最小值。

③不断地作贪心选择，选择路径最小值最小的结点来加入U。

④每当一个结点加入U后，更新源结点到U外V内的其他结点路径最小值。

⑤当所有结点都加入到U中后即算法完成。

2.Dijkstra算法思想

加入集合U=确定路径？能确保是最短路径吗？下面进行分析：

1.初始化时集合U内只有源节点。考虑加入U的第一个节点：

当要选择第一个加入U的结点时，我们选择与源节点有边且边权值最小的节点。为什么呢？因为源结点到此结点的距离走这条边肯定是最短的。

举个例子：假设源结点v，与它与边关系的只有结点a、b，且v→a=10，v→b=20。

如果v→a这条边被你放弃的话，再想要从v走到a就必须经过v→b→其他节点→a。代价至少是20+，必大于10。

所以此时将a加入U是最好的，源节点到a的距离肯定是最短的。

2.考虑后来加入集合的其他节点：

①第一步：先计算源结点v到达U外的各结点的最小路径长度。

从第一个结点的加入说明了：U内的点都是已经确定由源节点走到它的最短距离了。所以源结点可以放心地借助U内的结点走到U外的结点，不会走弯路。

用上个例子继续举例：对于U外的结点b，源结点v到它的路径有多种选择，如v->a->b、v->b这两条路径，选择路径代价最小的就是v到b的最小路径长度。

②第二步：在这些U外结点的各自的最小路径长度中选择最小的那个结点，将其加入集合。

继续用例子举例：

假设现在集合外的结点有c、d，且存在c到达d的边，权值为10。现计算得到v到达c的最短路径长度为30，v到达d的最短路径长度为50。

如果先将c加入集合，v到d的路径又多出一条：v->U内其他结点->c->d，代价为40。可以将v到达d的最短路径长度更新为40了。

而若是先将d加入集合，v到c的路径也会多出一条：v->U内其他结点->d->c。但是代价为60，对v到c的最短路径长度更新没有什么作用。

所以总是贪心地选择最短路径长度小的加入集合，它可能会帮助我们更新源节点到U外其他结点的最短路径长度。

三、具体案例分析

四、具体代码实现

public class SingleSourceShortestPath {
 
	public static void main(String[] args) {
 
		//节点数量
		int num = 5;
		//源节点
		int sourcev = 1;
		
		/*
		 * 5个节点，但设邻接矩阵为c[6][6]
		 * 这样c[1][2]就表示第一个节点到第二个节点的距离，较好理解
		 * 故：
		 * 因没有第0个节点，邻接矩阵第一行、第一列作废，设为-1
		 * 因节点自身到自身无意义，邻接矩阵左至右对角线作废，设为-1
		 */
		int[][] c = {{-1,-1,-1,-1,-1,-1},
					 {-1,-1,10,-1,30,100},
					 {-1,10,-1,50,-1,-1},
					 {-1,-1,50,-1,20,10},
					 {-1,30,-1,20,-1,60},
					 {-1,100,-1,10,60,-1}};
		
		//结果
		int[][] result = dijkstra(num,c,sourcev);
		for (int i = 1; i <= num; i++) {
			System.out.print("节点" + i + ":");
			if(i == sourcev) {
				System.out.println("该节点为源节点!");
			}else {
				System.out.print("到源节点最短路径为" + i + "->");
				int index = result[0][i];
				while(index != sourcev) {
					System.out.print(index + "->");
					index = result[0][index];
				}
				System.out.println(sourcev + ",长度为" + result[1][i]);
			}
		}
	}
 
	/**
	 * 
	 * @param num 节点的数量
	 * @param c 邻接矩阵
	 * @param sourcev 源节点
	 * @return 一个数组，数组的第0行表示节点的前驱节点，数组的第1行表示源到节点的距离。
	 */
	private static int[][] dijkstra(int num, int[][] c, int sourcev) {
		
		int[][] prevANDdist = new int[2][num+1];
		boolean[] isChosen = new boolean[num+1];
		
		//初始化
		for (int i = 1; i < prevANDdist[0].length; i++) {
			if(i == sourcev) {
				prevANDdist[0][i] = -1;
				prevANDdist[1][i] = Integer.MAX_VALUE;
				isChosen[sourcev] = true;
			}else {
				if(c[i][sourcev] != -1) {
					prevANDdist[0][i] = sourcev;
					prevANDdist[1][i] = c[i][sourcev];
					isChosen[i] = false;
				}else {
					prevANDdist[0][i] = -1;
					prevANDdist[1][i] = Integer.MAX_VALUE;
					isChosen[i] = false;
				}
			}
		}
		
		//因为要依次加入除去源节点外的num-1个节点，所以要循环num-1次。
		for (int i = 1; i <= num-1; i++) {
			int tempv = 0;
			int tempdist = Integer.MAX_VALUE;
			//选取下一个节点
			for (int j = 1; j <= num; j++) {
				if(isChosen[j]==false && prevANDdist[1][j]<tempdist) {
					tempv = j;
					tempdist = prevANDdist[1][j];
				}
			}
			//确认下一个节点是谁后做出的对表的更新
			isChosen[tempv] = true;
			for (int j = 1; j <= num; j++) {
				if(isChosen[j]==false && c[tempv][j] != -1) {
					if(prevANDdist[1][tempv] + c[tempv][j] < prevANDdist[1][j]) {
						prevANDdist[0][j] = tempv;
						prevANDdist[1][j] = prevANDdist[1][tempv] + c[tempv][j];
					}
				}
			}
		}
		
		return prevANDdist;
	}
}

五、Dijkstra算法与Prim算法的区别

注：如果你知道什么是Prim算法，可以看一下。不知道的话也无所谓，跟本文关系不大。

Dijkstra算法与Prim算法的区别在于：

1.在图论中，Prim算法解决的问题是连通无向有权图中最小生成树问题，而Dijkstra算法解决的问题是源点到目标点的最短路径问题。

2.虽然这两个算法在添加新结点时，都是选择“距离最短”的结点加入集合，但是Prim算法中，“距离最短”是指未访问的结点到已经访问的所有结点的距离最小，将已经访问的结点视为一个整体。而在Dijkstra算法中，“距离最短”是指所有未访问结点到源结点距离最小（通过已访问的结点）。

3. 在Prim算法中，数组元素dist[i]表示未访问结点i到已访问结点集合的最短距离，所以此时需要len记录最短距离。而Dijkstra算法中，数组元素dis[i]表示未访问结点i到源点的最短距离。