1 问题描述
    何为Dijkstra算法？
    Dijkstra算法功能：给出加权连通图中一个顶点，称之为起点，找出起点到其它所有顶点之间的最短距离。
    Dijkstra算法思想：采用贪心法思想，进行n-1次查找（PS:n为加权连通图的顶点总个数，除去起点，则剩下n-1个顶点），第一次进行查找，找出距离起点最近的一个顶点，标记为已遍历；下一次进行查找时，从未被遍历中的顶点寻找距离起点最近的一个顶点， 标记为已遍历；直到n-1次查找完毕，结束查找，返回最终结果。

    2 解决方案
    迪杰斯特拉，最短路径 - 图1

    迪杰斯特拉，最短路径 - 图2
    3 题意：
    例题： POJ_2387
    迪杰斯特拉算法的特点 ：
    1.没有 负权值的图
    2.给定了起点和终点的图

    不进行点的标记，只进行权值的比较
    示例代码：

    1. package tuLun;
    3. import java.io.BufferedReader;
    4. import java.io.IOException;
    5. import java.io.InputStreamReader;
    6. import java.util.ArrayList;
    7. import java.util.Arrays;
    8. import java.util.PriorityQueue;
    9. import java.util.StringTokenizer;
    11. public class A_迪杰斯特拉_test {
    12.     static int N,M;
    13.     static ArrayList<ArrayList<int[]>> nodeArryList;
    14.     static PriorityQueue<nodePoint> pQueue;
    15.     static int[] pointDis;  //记录到达当前节点的最大值
    16.     static class nodePoint implements Comparable<nodePoint>{
    17.         int getPoint;
    18.         int vule;
    19.         public nodePoint(int getPoint, int vule) {
    20.             this.getPoint = getPoint;
    21.             this.vule = vule;
    22.         }
    23.         //重写 compareTo 方法
    24.         @Override
    25.         public int compareTo(nodePoint o) {
    26.             return this.vule == o.vule? this.getPoint-o.getPoint : this.vule -o.vule;
    27.         }
    28.     }
    29.     public static void main(String[] args) throws IOException {
    30.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    31.         StringTokenizer st = new StringTokenizer(br.readLine());
    32.         N = Integer.parseInt(st.nextToken());  //边
    33.         M = Integer.parseInt(st.nextToken());  //点
    35.         nodeArryList = new ArrayList<ArrayList<int[]>>();
    36.         for (int i = 0; i <= M; i++) {
    37.             nodeArryList.add(new ArrayList<int[]>());
    38.         }
    39.         pointDis = new int[M+1];
    40.         Arrays.fill(pointDis, Integer.MAX_VALUE);
    41.         for (int i = 0; i < N; i++) {
    42.             st = new StringTokenizer(br.readLine());
    43.             int s = Integer.parseInt(st.nextToken());
    44.             int e = Integer.parseInt(st.nextToken());
    45.             int v = Integer.parseInt(st.nextToken());
    46.             nodeArryList.get(s).add(new int[] {e,v});
    47.             nodeArryList.get(e).add(new int[] {s,v});
    48.         }
    49.         getMinPath(1);
    50.         System.out.println(pointDis[M]);
    51.     }
    52.     private static void getMinPath(int i) {
    53.         pointDis[i] = 0;  //第一节点的  dis  最小值 设置维0
    54.         pQueue = new PriorityQueue<nodePoint>();
    55.         pQueue.add(new nodePoint(i, 0));  //加入第一个节点， 高达的点为1，到达1节点，需要的权值设定为 0
    56.         while(!pQueue.isEmpty()) {
    57.             nodePoint tempNode = pQueue.poll();
    58.             int getPoint = tempNode.getPoint;
    59.             for (int j = 0; j < nodeArryList.get(getPoint).size(); j++) {
    60.                 int getPointTemp = nodeArryList.get(getPoint).get(j)[0];
    61.                 int getPointDis = pointDis[getPointTemp];
    62.                 int getValTemp = nodeArryList.get(getPoint).get(j)[1];
    63.                 //节点没有被访问过 ，并且当前节点的值（dis） + 下一个节点的权值  < 下一个点中记录的节点最小值（dis）   ，因为时求最短路经
    64.                 if (getPointDis > getValTemp+pointDis[getPoint]) {
    65.                     pointDis[getPointTemp] = getValTemp+pointDis[getPoint];
    66.                     pQueue.add(new nodePoint(getPointTemp, getValTemp));
    67.                 }
    68.             }
    69.         }
    70.     }
    71. }