Dijkstra算法Java实现

一、原文链接

http://blog.csdn.net/u011638883/article/details/17200869
原文是关于Dijkstra算法的解释与实现。还是老话x 如有侵权，立即删除。

二、算法理解

以下是我按照个人理解扯的。
最短路径算法的实现实际上是将图上所有点分为两个集合，一个是未加入的点的集合A，一个是已加入的点的集合B。一开始只有起点S在集合中，每次遍历所有点都会选出路径最短的点加入集合B中，并更新最短路径。
当集合B中找到目标点或者集合A中没有点时，将跳出循环。

三、代码实现

import java.util.Scanner;
import java.util.*;

public class Main {

    private static int IMAX = 10000; //不连通状态
public static int[][] adjMat ={
        {0,1,3,6},
        {1,0,IMAX,6},
        {3,IMAX,0,2},
        {6,6,2,0}
};

    public static void main(String[] args) {

        Dijkstra(adjMat,0,3);
    }

    public static void LoopNode(){
        Node head = new Node();
        Node temp = head;
        for (int i = 0;i<10;i++){
            temp.val = i;
            temp.next = new Node();
            temp = temp.next;
        }
        temp.val = 10;
        temp.next = head;

        Node node1,node2;
        node1 = node2 = head;
        while (true){
            node1 = node1.next;
            node2 = node2.next.next;
            if (node1 == node2)
                break;
        }

        System.out.println("is Loop");

    }

    public static void Dijkstra(int[][] martix,int start,int terminal){
        boolean []isVisted = new boolean[martix.length];
        int []d = new int[martix.length];
        for (int i = 0;i<martix.length;i++){
            isVisted[i] = false; //该点是否被计入，可以理解为判断该点是否已经加入集合B
            d[i] = IMAX;//在当前的集合B所能连接的路径中，从起始点到该点的最短路径
        }
        isVisted[start] = true;
        d[start] = 0;
        int unVisitNode = martix.length ;
        int index = start;
        while (unVisitNode > 0 && !isVisted[terminal] ){
            int min = IMAX;
            //选出集合A中的点到集合B的路径最短的点
            for (int i = 0;i<d.length;i++){
                if (min > d[i] && !isVisted[i]){
                    index = i;
                    min = d[i];
                }
            }
            
            
        for (int i = 0;i<martix.length;i++){
                if (d[index] + martix[index][i] < d[i]) //更新当前的最短路径
                    d[i] = d[index] + martix[index][i];
        }

        unVisitNode -- ;
            isVisted[index] = true;
        }

        System.out.println(d[terminal]);
    }