Dijkstra无向图

算法执行步骤如下：

上面两张图来源于：http://blog.csdn.net/v_july_v/article/details/6096981

很牛的大神，膜拜，此处有鲜花

Dijkstra 的算法实现

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class Dijkstra {

    List<verPoint>Graph;

    public List<verPoint> getGraph() {

        return Graph;

    }

    public void setGraph(List<verPoint> graph) {

        Graph = graph;

    }

    public double minDistance(double minD,Map<Integer,Double>distance,List<verPoint>Graph,List<verPoint>S,List<verPoint>U){

        if(S==null){

            S = new ArrayList();

            U = new ArrayList();

            S.add(Graph.get(0));

            for(int i = 0;i<Graph.size();i++){

                if(!S.contains(Graph.get(i))){

                    U.add(Graph.get(i));

                }

            }

        }

        if(S.size()==Graph.size()){

            return minD;

        }

        verPoint nowPoint = S.get(S.size()-1);

        Map <Integer,Double>newdistance = new HashMap();

        double []dis = new double[U.size()];

        for(int i = 0;i<U.size();i++){

            dis[i] = minD + nowPoint.distancePoint(U.get(i));//直接加上到U.get(i)的距离

            if(dis[i]>distance.get(U.get(i).getId())){//与上一次到U.get(i)距离的比较

                dis[i]=distance.get(U.get(i).getId());

            }

            newdistance.put(U.get(i).getId(), dis[i]);

        }

        //寻找dis中最小的值所对应的索引值

        int mindex = 0;

        for(int i = 1;i<dis.length;i++){

            if(dis[mindex]>dis[i]){

                mindex = i;

            }

        }

        double newMinD = dis[mindex];

        S.add(U.get(mindex));

        U.remove(mindex);

        for(int i = 0;i<S.size();i++){

            System.out.print("  "+S.get(i).getVerName());

        }

        System.out.println();

        double min = minDistance(newMinD,newdistance,Graph,S,U);

        return min;

    }

}

应当注意的是：

1、minD存储的是每次搜寻后当前点与初始点之间的最小距离

2、distance中存储的是仍在open中的点到初始点的最小距离

3、每次循环的时候，首先将未在S中的点放入U中。S表示路径，U表示剩余点；

其次，计算S最后面的一点到U中每个点的距离，并且如果上一次也到过U中某个节点，则注意比较这两次到同一节点的距离，取更小的。然后取U中各节点最小距离，并放入S中直至S中元素等于图的元素个数