욕심 전략의 풀이 단일 소스 최 단 경로 - 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)));

	}

}