算法笔记（第二部分）-- 图算法之Dijkstra最短路径算法

Dijkstra算法由著名的荷兰计算机科学家Dijkstra于1959年提出（这位老人家已于2002年过世，过世前任教于University Of Texas，Austin）。简单的说，这个算法解决的就是对于图中的任意一个节点，求出该点到其他节点的最短路径。

Dijkstra算法过程：
1. 创建一个节点之间的距离表，一个目标节点上一个节点表，一个访问过的节点表和一个当前节点。
2. 初始化距离表值，初始节点设为0，其他设为无穷大。
3. 所有访问过的节点表中的值设为“false”。
4. 将目标节点上一个节点链表中的值设为“undefined”。
5. 当前节点设置为初始节点。
6. 将当前节点设置为“visited”。
7. 根据图的结构更新距离表与目标节点上一个节点表。
8. 更新从初始节点到目标节点的最短路径：当前节点->未访问过节点＋初始节点->当前节点。
9. 重复步骤6-8直至所有节点都遍历完。

算法动画演示（个人觉得做得很好）：http://www.cs.usfca.edu/galles/visualization/visualization.jar

Dijkstra算法简易实现

package com.interview.graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.List;
import java.util.Map.Entry;

public class DijkstraAlgorithm {
    public static int LARGE_NUMBER = 10000;
    public static String UNDEFINED = "undefined";
	
	public Hashtable<String, String> DijkstraAlgorithm(Hashtable<String, Hashtable<String, Integer>> ajacencyList, String source){
		//store shortest path from source to current calculating point
		Hashtable<String, Integer> distance = new Hashtable<String, Integer>();
		//store the paths
		Hashtable<String, String> previous = new Hashtable<String, String>();
		//store all need to be computed nodes
		List<String> nodes = new ArrayList<String>();
		
		//inialize the dist and previous;
		for (Entry<String, Hashtable<String, Integer>> entry : ajacencyList.entrySet()) {
			String key = entry.getKey();
			distance.put(key, LARGE_NUMBER);
			previous.put(key, UNDEFINED);
			nodes.add(key);
		}		
		distance.put(source, 0);
		
		String nextNode;
		Hashtable<String, Integer> neighbors;
		while(!nodes.isEmpty()){
			nextNode = findNode(distance, nodes);
			nodes.remove(nextNode);
			neighbors = ajacencyList.get(nextNode);						
			//make sure the shortest path from source to the destination
			for(Entry<String, Integer> entry : neighbors.entrySet()){
				int alt =  (distance.get(nextNode)).intValue()+entry.getValue();
				String neighbor = entry.getKey();
				if(alt<(distance.get(neighbor)).intValue()){
					distance.put(neighbor, alt);
					previous.put(neighbor, nextNode);
				}
			}
		}
		return previous;
	}
	
	//find the lowest cost between point A and point B
	public String findNode(Hashtable<String, Integer> dist, List<String> nodes){
    	int distance = LARGE_NUMBER;
    	String node = "";
    	for(Entry<String, Integer> entry : dist.entrySet()){
    		String key = entry.getKey();
    		if(nodes.contains(key)){
    			int value = entry.getValue().intValue();
    			if(value<distance){
    				distance = value;
    				node = key;
    			}
    		}
    	}
    	return node;
    }
        //print the route from source to target
	public void printOutPath(Hashtable<String, String> path, String source, String target) {
		for (Entry<String, String> entry : path.entrySet()) {
    		String currentNode = entry.getKey();
    		String previousNode = entry.getValue();
    		if (currentNode.equals(target)) {
    			List<String> pathList = new ArrayList<String>();
        		pathList.add(currentNode);
        		if (!UNDEFINED.equals(previousNode)) {
        			pathList.add(previousNode);
        		}   		
        		while (!previousNode.equals(source)&&!previousNode.equals(UNDEFINED)) {
        			previousNode = path.get(previousNode);
        			pathList.add(previousNode);
        		}
        		Collections.reverse(pathList);    		
        		int index = 0;
        		for (String node : pathList) {
        			System.out.print(node);
        			if (index!=pathList.size()-1) {
        				System.out.print("->");
        			}
        			index++;
        		}
        		System.out.println();
        		break;    		
    		}   		    				
    	}
	}
	//print out all routes from the source
	public void printOutRoutes(Hashtable<String, String> path, String source){
		for (Entry<String, String> entry : path.entrySet()) {
    		String currentNode = entry.getKey();
    		String previousNode = entry.getValue();
    		
    		List<String> pathList = new ArrayList<String>();
    		pathList.add(currentNode);
    		if (!UNDEFINED.equals(previousNode)) {
    			pathList.add(previousNode);
    		}   		
    		while (!previousNode.equals(source)&&!previousNode.equals(UNDEFINED)) {
    			previousNode = path.get(previousNode);
    			pathList.add(previousNode);
    		}
    		Collections.reverse(pathList);    		
    		int index = 0;
    		for (String node : pathList) {
    			System.out.print(node);
    			if (index!=pathList.size()-1) {
    				System.out.print("->");
    			}
    			index++;
    		}
			System.out.println();
    	}
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Hashtable<String, Hashtable<String, Integer>> graph = new Hashtable<String, Hashtable<String,Integer>>();
		
		Hashtable<String, Integer> neighbors1 = new Hashtable<String, Integer>();
		neighbors1.put("B", 2);
		neighbors1.put("C", 1);		
		graph.put("A", neighbors1);

		Hashtable<String, Integer> neighbors2 = new Hashtable<String, Integer>();
		neighbors2.put("D", 3);
		graph.put("B", neighbors2);
		
		Hashtable<String, Integer> neighbors3 = new Hashtable<String, Integer>();
		neighbors3.put("D", 1);
		graph.put("C", neighbors3);
		
		Hashtable<String, Integer> neighbors4 = new Hashtable<String, Integer>();
		neighbors4.put("E", 2);
		neighbors4.put("F", 3);
		graph.put("D", neighbors4);
		
		Hashtable<String, Integer> neighbors5 = new Hashtable<String, Integer>();
		graph.put("E", neighbors5);
		
		Hashtable<String, Integer> neighbors6 = new Hashtable<String, Integer>();
		graph.put("F", neighbors6);
		
		DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();
		Hashtable<String, String> path = dijkstra.DijkstraAlgorithm(graph, "A");
		dijkstra.printOutRoutes(path, "A");
		dijkstra.printOutPath(path, "A", "E");

	}

}

在这个简易实现中，因为节点之间的距离为1，我就是用了简化版的邻接表（Hashtable）。代码应该很容易能看懂，核心：1. 从距离表中找出未访问过的拥有初始节点至该节点最小距离的作为下一个计算节点 2.若当前节点->未访问节点＋初始节点->当前节点的值小于记录则进行替换，直至所有节点都被访问。算法写的不是很优，希望各位多多拍砖。

评论

1 楼 cywhoyi 2010-01-30  

非常感谢