贪心策略之求解单源最短路径-Dijkstra算法

对于单源最短路径问题，可以利用贪心策略求解，其经典算法便是Dijkstra算法。首先找出与v0点最邻近点的最短路径，然后找出与v0点第二近顶点的最短路径，直到找到最后一个点与v0的最短路径。

 

实现Dijkstra算法可以和prim算法类似，需要构造2个集合s1,s2。其中s1是当前搜索到的最短路径顶点集，s2是剩下的带求解的点集。每一次搜索都会将s2中的点与最后加入到s1的点进行权值更新操作，一旦发现有s1到s2的更短的路径，就更新目前的距离集合，并且将最短距离对应的那个点加入到s1中，并从s2中删除。

 

Dijkstra算法的时间复杂度是O(n^2)。

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 单源最短路径的Dijkstra算法实现
 * @author ql_math
 *
 */
public class DijkstraShortestPath {
	
	/**最短路径的连接*/
	private double[] shortestPathArray;
	
	private int pointsNum;

	
	/**
	 * Dijkstra算法计算单源最短路径
	 * @param pIndex
	 * @param graphicArray
	 * @return
	 */
	public double[] calculateShortestPath(int pIndex, double[][] graphicArray)
	{
		SimpleGraphics graph=new SimpleGraphics(graphicArray);
		pointsNum=graph.getPSize();//顶点数目
		
		List<Integer> curFoundList=new LinkedList<Integer>();//当前找到的点集合
		curFoundList.add(pIndex);
		
		List<Integer> midList=new LinkedList<Integer>();//待查找点集
		
		shortestPathArray=new double[pointsNum];//获得与当前点连接的点集合
		initShortestPath(midList,pIndex);//待查找点集

		int set_num=1;
		while(set_num<=pointsNum)
		{
			int cur_shortest_index=calculateP2PShortestPath(graph,curFoundList,midList);//找出与当前点连接的点距最小值的点
			
			curFoundList.add(cur_shortest_index);
			midList.remove(new Integer(cur_shortest_index));

			set_num++;
		}
		
		return shortestPathArray;
	}

	private int calculateP2PShortestPath(SimpleGraphics graph, List<Integer> curFoundList, List<Integer> midList) {
		int compareNode=((LinkedList<Integer>)curFoundList).getLast();
		double[] array=graph.getAdjacencyPoints(compareNode);
		double min=Double.MAX_VALUE;
		int index=0;	

		for(int i=0;i<pointsNum;i++)
		{
			double newLen=shortestPathArray[compareNode]+array[i];
			
			if(newLen<shortestPathArray[i]&&midList.contains(i))
				shortestPathArray[i]=newLen;
		}

		for(int i=0;i<pointsNum;i++)
		{
			if(shortestPathArray[i]<min&&midList.contains(i))
			{
				index=i;
				min=shortestPathArray[i];
			}
		}
		return index;
	}


	/**
	 * 初始化
	 * @param n
	 * @param index
	 */
	private void initShortestPath(List<Integer> list, int index) {
		
		for(int i=0;i<pointsNum;i++)
		{
			if(i!=index)
			{
				list.add(i);
				shortestPathArray[i]=Double.MAX_VALUE;
			}

		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		DijkstraShortestPath dj=new DijkstraShortestPath();
		double[][] graphicArray={{0,1,6,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE},
				{1,0,3,4,6,Double.MAX_VALUE},{6,3,0,2,2,Double.MAX_VALUE},
				{Double.MAX_VALUE,4,2,0,2,3},{Double.MAX_VALUE,6,2,2,0,4},{Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,3,4,0}};
		System.out.println("最短路径："+Arrays.toString(dj.calculateShortestPath(0,graphicArray)));

	}

}