TU

package algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 迪克斯特拉算法
 * Dijkstra是基于加权有向图，输出最短路径的方法。
 * 
 * 算法：(1) 找出最便宜的节点，即可在最短时间内前往的节点。
 *      (2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
 *      (3) 重复这个过程，直到对图中的每个节点都这样做了。
 *      (4) 计算最终路径。
 * 
 * 
 * @author natty
 *
 */

public class Dijkstra {
    
    private Map<String,Map<String,Integer>> graph;
    
    public Dijkstra(Map<String,Map<String,Integer>> graph) {
        this.graph = graph;
    }
    
    public int getShortestPath(String node) {
        //每个node的权重先给最大值，排除掉起点
        HashMap<String,Integer> node_status = new HashMap<String,Integer>();
        for(Map.Entry<String,Map<String,Integer>> entry : this.graph.entrySet() )
        {
            if(!entry.getKey().equals("start"))
                node_status.put(entry.getKey(), Integer.MAX_VALUE);
        }
        

        node_status.putAll(this.graph.get("start"));
        
        ArrayList<String> already_checked = new ArrayList<String>();
        Map<String,Integer> checked_node = new HashMap<String,Integer>();
        
        while(node_status != null)
        {
            String tdf = find_min_node(node_status);
            if(!tdf.equals("end")) {
                //更新node_status
                for(Map.Entry entry : graph.get(tdf).entrySet())
                {
                    if(  !already_checked.contains(tdf) &&
                        (node_status.get(tdf) + (int)entry.getValue()) 
                        < node_status.get(entry.getKey())   
                            ) 
                    {
                        node_status.put((String) entry.getKey(), (node_status.get(tdf) + (int)entry.getValue()));
                    }
                }
            }
            else
                break;
            checked_node.put(tdf, node_status.get(tdf));
            already_checked.add(tdf);
            node_status.remove(tdf);
            
            System.out.println(printMap(checked_node));
            System.out.println("***********************");
            
        }
        
        int sum = 0 ;
        for (Map.Entry entry : checked_node.entrySet()) {
            sum += (int)entry.getValue();
        }
        
        return sum;
    }
    
    private String find_min_node(Map<String, Integer> node_status) {
        String min_key = "" ;
        int min_value = Integer.MAX_VALUE;
        for(Map.Entry entry : node_status.entrySet())
        {
            if ((int)entry.getValue() < min_value) {
                min_value = (int)entry.getValue();
                min_key = String.valueOf(entry.getKey());
            }
        }
        return min_key;
    }
    
    private String printMap(Map<String,Integer> maps)
    {
        String output = "";
        for( Map.Entry tdfs: maps.entrySet())
        {
            output = tdfs.getKey() + " -> " + tdfs.getValue();
        }
        return output;
    }
    
    

    public static void main(String[] args) {
        
        //构建有向加权图
        Map<String,Map<String,Integer>> graph = 
                new HashMap<String,Map<String,Integer>>();
        Map<String,Integer> start = new HashMap<String,Integer>();
        start.put("node1", 5);
        start.put("node2", 0);
        graph.put("start",start);
        Map<String,Integer> node1 = new HashMap<String,Integer>();
        node1.put("node3", 15);
        node1.put("node4", 20);
        graph.put("node1",node1);
        Map<String,Integer> node2 = new HashMap<String,Integer>();
        node2.put("node3", 30);
        node2.put("node4", 35);
        graph.put("node2",node2);
        Map<String,Integer> node3 = new HashMap<String,Integer>();
        node3.put("end", 20);
        graph.put("node3",node3);
        Map<String,Integer> node4 = new HashMap<String,Integer>();
        node4.put("end", 10);
        graph.put("node4",node4);
        graph.put("end",null);
        
        Dijkstra dj = new Dijkstra(graph);
        System.out.println(dj.getShortestPath("end"));
        

    }

}