一、加权有向图

• 一幅由V个顶点和E条有方向有权重的边构成的图

package 图;

public class DirectedEdge {
    private int v;//顶点
    private int w;//顶点
    private double weight;//权重

    public DirectedEdge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
//起点
    public int from() {
        return v;
    }
//终点
    public int to() {
        return w;
    }

    public double getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return String.format("%d-%d  %.2f",v,w,weight);
    }
}

package 图;

import java.util.LinkedList;
import java.util.Queue;

public class EdgeWeightedDigraph {
    private int V;//顶点数
    private int E;//边
    private Queue<DirectedEdge>[] adj;//邻接表

    public EdgeWeightedDigraph(int v) {
        V = v;
        E=0;
        adj=new Queue[v];
        for (Queue<DirectedEdge> queue : adj) {
            queue=new LinkedList<>();
        }
    }
    public void addEdge(DirectedEdge edge){
        int v=edge.from();
        int w=edge.to();
        adj[v].offer(edge);
        E++;
    }

    public Queue<DirectedEdge> adj(int v) {
        return adj[v];
    }
    public Queue<DirectedEdge> edges(){
        Queue<DirectedEdge> queue=new LinkedList<>();
        for (Queue<DirectedEdge> edges : adj) {
            for (DirectedEdge edge : edges) {
                queue.add(edge);
            }
        }
        return queue;
    }

    public int getV() {
        return V;
    }

    public int getE() {
        return E;
    }
}

二、最短路径问题

• 最短路径问题：找到一个顶点到达另一个顶点的成本最小的路径
• 性质： 路径有向；权重不一定等于距离；并不是所有顶点可达；负权重问题；存在多条最短路径；可能存在平行边和自环
• 最短路径树：树的每条路径都是最短路径
• 松弛技术：放松边v-w意味着检查从s到w的最路路径是否是先从s-v，在v-w，如果是，则更新数据结构，即disTo[v]+e.weight()>disTo[w]，则这条边可以忽略，否则更新edgeTo[w]和disTo[w]

  private void relax(EdgeWeightedDigraph digraph,int v){
        for (DirectedEdge edge : digraph.adj(v)) {
            int w= edge.to();
            if(disTo[w]>disTo[v]+edge.getWeight()){
                disTo[w]=disTo[v]+edge.getWeight();
                edgeTo[w]=edge;
            }
        }
    }

三、Dijkstra 算法

• 能够解决边权重非负的加权有向图的单起点最短路径问题

package 图;

public class DijkstraSP {
private DirectedEdge[] edges;//记录经过该顶点的上一条边
    private double[] distTo;//记录经过该顶点的距离
    private IndexMinPQ<Double> pq;//索引优先队列，，将索引和权重的优先级关联起来，可以删除并返回权重最小的索引（顶点）

    public DijkstraSP(EdgeWeightedDigraph digraph,int s) {
        edges=new DirectedEdge[digraph.getV()];
        distTo=new double[digraph.getV()];
        pq=new IndexMinPQ<>(digraph.getV());
        for (int i = 0; i < distTo.length; i++) {
            distTo[i]=Double.POSITIVE_INFINITY;
        }
        distTo[0]=0.0;
        pq.insert(s,0.0);
        while (!pq.isEmpty()){
            int v=pq.delMin();
            relax(digraph,v);
        }
    }

    private void relax(EdgeWeightedDigraph digraph, int v) {
        for (DirectedEdge edge : digraph.adj(v)) {
            int w=edge.to();
            if(distTo[w]>distTo[v]+edge.getWeight()){
                distTo[w]=distTo[v]+edge.getWeight();
                edges[w]=edge;
                if(pq.contains(w)){
                    pq.change(w,distTo[w]);
                }else {
                    pq.insert(w,distTo[w]);
                }
            }
        }
    }
}