单源最短路径算法---Dijkstra算法

给定一个赋权图G(V,E)和一个特定顶点s作为输入，找出从s到其他每一个其他顶点的最短赋权路径。权值为非负。

/*
 * Dijkstra算法实现
 */
import java.util.*;

public class ShortestWay {

    public static ArrayList<Vertex> verList = new ArrayList<>(); //存放所有顶点

    public static void main(String[] args) {
        Vertex v1 = new Vertex("V1",0);
        Vertex v2 = new Vertex("V2",1);
        Vertex v3 = new Vertex("V3",2);
        Vertex v4 = new Vertex("V4",3);
        Vertex v5 = new Vertex("V5",4);
        Vertex v6 = new Vertex("V6",5);
        Vertex v7 = new Vertex("V7",6);

        verList.add(v1);
        verList.add(v2);
        verList.add(v3);
        verList.add(v4);
        verList.add(v5);
        verList.add(v6);
        verList.add(v7);

        v1.addEdge(v2, 2);
        v1.addEdge(v4, 1);
        v2.addEdge(v4, 3);
        v2.addEdge(v5, 10);
        v3.addEdge(v1, 4);
        v3.addEdge(v6, 5);
        v4.addEdge(v3, 2);
        v4.addEdge(v5, 2);
        v4.addEdge(v6, 8);
        v4.addEdge(v7, 4);
        v7.addEdge(v6, 1);

        v1.setDistance(0);

        PriQueue pq = new PriQueue(verList);

        while(!pq.isEmpty()){
            Vertex ele = pq.removeEle();
            ArrayList<Vertex> adjList = ele.getAdjList();
            for(Vertex v : adjList){
                pq.changeEle(ele, v);
            }
        }
        System.out.print(verList);
    }
}

/*
 * 带权的边
 */
class WeightEdge{
    Vertex start;
    Vertex end;
    int weight;

    public WeightEdge(Vertex s,Vertex e,int w){
        this.start=s;
        this.end=e;
        this.weight=w;
    }

    public boolean equal(Vertex s,Vertex e){
        if(this.start.equals(s)&&this.end.equals(e)){
            return true;
        }
        return false;
    }

    public int getWeight(){
        return weight;
    }

}

/*
 * 顶点
 */
class Vertex{
    public static final int LIMIT = 1000; //用以代替无穷大
    public String name;
    public int index;
    public int distance; //距离
    ArrayList<Vertex> list = new ArrayList<>(); //存放邻接点
    ArrayList<WeightEdge> edges = new ArrayList<>(); //存放以此顶点为出发点的边

    public Vertex(String name,int index){
        this.name=name;
        this.index=index;
        distance = LIMIT;
    }

    //添加带权的边
    public void addEdge(Vertex e,int w){
        WeightEdge we = new WeightEdge(this, e, w);
        edges.add(we);
        addAdjList(e);
    }

    //添加邻接点
    public void addAdjList(Vertex b){
        list.add(b);
    }

    //获取对应两点的边的权
    public int getEdgeWeight(Vertex s,Vertex e){
        for(WeightEdge we : edges){
            if(we.equal(s, e)){
                return we.getWeight();
            }
        }
        return 0;
    }

    public ArrayList<Vertex> getAdjList(){
        return list;
    }

    public void setDistance(int dis){
        this.distance=dis;
    }

    public String toString(){
        return name+" "+this.getDistance();
    }

    public int getIndex(){
        return index;
    }

    public int getDistance(){
        return distance;
    }

    public boolean equals(Object obj){
        return this.name.equals(((Vertex)obj).name);
    }

}

/*
 * 优先队列
 */
class PriQueue{

    LinkedList<Vertex> que = new LinkedList<>();

    public PriQueue(ArrayList<Vertex> list){
        que.addAll(list);
    }

    //获得距离最小的顶点并删除
    public Vertex removeEle(){
        Vertex v = findMin();
        que.remove(v);
        return v;
    }

    //改变顶点距离
    public void changeEle(Vertex v1,Vertex v2){
        int weight = v1.getEdgeWeight(v1, v2);
        if(v1.getDistance()+weight<v2.getDistance()){
            v2.setDistance(v1.getDistance()+weight);
        }
    }

    public Vertex findMin(){
        int a = Vertex.LIMIT;
        Vertex v=null;
        Iterator<Vertex> it = que.iterator();
        while(it.hasNext()){
            Vertex tmp = it.next();
            int tmpDis = tmp.getDistance();
            if(a > tmpDis){
                a = tmpDis;
                v = tmp;
            }
        }
        return v;
    }

    public boolean isEmpty(){
        return que.isEmpty();
    }
}