图解Dijkstra算法过程(java代码实现)

weblog 精帖
2352

前言

 之前的博客中提到了floyd最短路径算法,此算法的优点是,简单易懂,核心算法代码只有5行,但是缺点是时间复杂度o(n3),时间复杂度太高。而下面要介绍的Dijkstra算法虽然设计上略有复杂,但是时间复杂度确能降低到o(n2)。

百科

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

问题案例

还以之前提到的那个路径问题为例,连图也是复制过来的。

Dijkstra的算法思路

1.把所有的节点分为两个集合分别是S集合(探索过程中已知的最短路径的节点的集合),U集合(暂未探索的节点的结合,但是每个节点到达开始节点的距离是可知的,并且是随着探索的过程,到达开始节点的距离是可以不断变化的)。

2.每次探索从U集合中取出距离开始节点最近的那个节点。并将该节点加入S集合,然后更新与该节点相邻的U集合中的各个节点与开始节点的距离(

具体的更新过程是:

如果从开始节点到该节点的距离+从该节点到该节点的相邻节点的距离>开始节点到邻节点的距离,那么就更新开始节点到邻节点的距离

例:开始节点到该节点的距离为a,从该节点到该节点的相邻节点的距离为b, 从开始节点到该节点的相邻节点的距离为c,那么if(a+b>c){c=a+b}

)。

3.如果还没有探索到目标节点,那就一直执行探索过程2,直到达到目标节点结束。
呕心沥血的总结~

伪算法

S=[];
U=[];
While(不是目标节点){
	K=从U集合中找出距离开始节点最近的节点。
	将k节点加入S集合并标记已探索该节点K
	//遍历U集合中所有的该节点的邻节点。
	For(i=0;i<a;i++){
		If(r[k][i]+r[start][k])<=r[start][i]){
			//更新权值
	        r[start][i]=r[k][i]+r[start][k];
        }
    }	
}

最后r[start][end]的值就是最短路径的距离。至于探索过程中经过的路径是什么~后边再说~

以上图为例,分解一下算法执行的过程

从节点1到节点4为例,从图中可以直接看出,从节点1直接到节点4距离为6,而从节点1经过节点2,再经过节点5到节点4的距离5。显然选择第二中方案更好。那么怎么做呢?

第一步先将开始节点1加入S集合

此时:S集合【1(0)  】    U集合【2(1)  3(8)  4(6)  5(∞)  】

第二步选择U集合中距离最小的节点2,加入S集合,并更新U集合中的距离。

此时:S集合【1(0)  2(1)  】        U集合【3(8)  4(6)  5(3)  】

第三步选择U集合中距离最小的节点5,加入S集合,并更新U集合中的距离。

此时:S集合【1(0)  2(1)  5(3)  】        U集合【3(6)  4(5)  】

第三步选择U集合中距离最小的节点4,加入S集合,并更新U集合中的距离。

此时:S集合【1(0)  2(1)  4(5)  5(3)  】    U集合【3(6)  】

这时已经遍历到目标节点4,所以从1节点到4的最短路径为5。

经过的路径为:[1, 2, 5, 4]

算法实现

算法中实现了求从开始节点到目标节点经过的路径,用一个数组parent保存经过该节点时的父节点。到达目标节点后可以用栈的结构反向推算出算法经过的路径。

package com.dzqc.yx;

import java.util.LinkedList;

/**
 * Dijkstra算法
 * @author jiajia
 */
public class Dijkstra {
	/**
	 * 	m 代表正无穷(两个节点之间无法直接到达)
	 */
	public static final int m=Integer.MAX_VALUE>>3;
	/**
	 *	邻接矩阵描述图
	 */
	public static final int r[][]=new int[][]{
		{0,0,0,0,0,0},
		{0,0,1,8,6,m},
		{0,m,0,m,m,2},
		{0,4,m,0,3,8},
		{0,1,m,15,0,10},
		{0,m,m,3,2,0}
	};
	/**
	 *	最短路径节点集合
	 */
	public static final int s[]=new int[r.length];
	/**
	 * 	父节点位置
	 */
	public static final int parent[]=new int[]{-1,-1,-1,-1,-1,-1};
	
	public static void main(String[] args) {
		int start=1;
		int end=4;
		dijkstra(start,end);
		for(int i=1;i<parent.length;i++) {
			System.out.print(i+":"+parent[i]+"\t");
		}
		System.out.println();
		System.out.println("经过路径:"+role(start,end));
	}
	
	public static LinkedList<Integer> role(int start,int end) {
		LinkedList<Integer> stack=new LinkedList<Integer>();
		stack.add(end);
		while(parent[end]!=-1) {
			stack.addFirst(parent[end]);
			end=parent[end];
		}
		stack.addFirst(start);
		return stack;
	}
	
	/**
	 * 	核心算法
	 * @param start
	 * @param end
	 */
	public static void dijkstra(int start,int end){
		/**
		 * 	第一个顶点放入s集合
		 */
		s[start]=1;
		prinf(start);
		int k = start;
		while(s[end]!=1) {
			/**
			 * 	从u集合中选取一个权值最小的节点k
			 */
			int min=m;
			for(int i=1;i<r.length;i++) {
				if(s[i]!=1&&r[start][i]<min) {
					min=r[start][i];
					k=i;
				}
			}
			s[k]=1;
			System.out.println("选择的点为:"+k);
			/**
			 * 	修改节点的权值
			 */
			for(int i=1;i<r.length;i++) {
				if(s[i]!=1&&(r[k][i]+r[start][k])<=r[start][i]) {
					r[start][i]=r[k][i]+r[start][k];
					parent[i]=k;
				}
			}
			prinf(start);
		}
		System.out.println();
		System.out.println("最短路:"+r[start][end]);
	}
	
	/**
	 * 	打印S集合和U集合
	 * @param start
	 */
	public static void prinf(int start) {
		System.out.println();
		System.out.print("S集合【");
		for(int i=1;i<r.length;i++) {
			if(s[i]!=0) {
				System.out.print(i+"("+r[start][i]+")  ");
			}
		}
		System.out.print("】\nU集合【");
		for(int i=1;i<r.length;i++) {
			if(s[i]!=1) {
				System.out.print(i+"("+r[start][i]+")  ");
			}
		}
		System.out.print("】");
	}
}

 

猜你喜欢