算法课 实验7

实验问题描述：

加权无向图最短路径查找，从一点到另外一点的最小路径，比如从成都到北京，途中有好多城市，如何规划路线，能够使总共的路线最短，如何使总共的费用最低

实验步骤（采用Dijkstra算法)：

• 加权有向图的实现

下面代码是加权有向图的边的数据结构

package DiEdge; //java的包管理

public class DiEdge {
    private int from;
    private int to;
    private double weight;

    public DiEdge(int from, int to, double weight) {
        this.from = from;
        
    }
}

有向的也会比无向的简单一些，因为两个顶点有明显的前后顺序。

下面是加权有向图的实现，加权图的生成

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class EdgeWeightedDiGraph<Item> {
    private int vertexNum; //顶点的个数
    private int edgeNum;   //边的个数
    // 不是领接表，是以单个顶点为中心向四周发散的一种数据结构
    private List<List<DiEdge>> adj;
    // 顶点信息，是一个列表，所有的列表信息都会呈现在这个list中
    private List<Item> vertexInfo; 

    //一下提供3种构造方法
    public EdgeWeightedDiGraph(List<Item> vertexInfo) {
        this.vertexInfo = vertexInfo;
        this.vertexNum = vertexInfo.size();
        adj = new ArrayList<>();
        for (int i = 0; i < vertexNum; i++) {
            adj.add(new LinkedList<>());
        }      
    }

    public EdgeWeightedDiGraph(List<Item> vertexInfo, int[][] edges, double[] weight) {
        this(vertexInfo);
        for (int i = 0; i < edges.length; i++) {
            Didge edge = new DiEdge(edges[i][0], edges[i][1], weight[i]);
            addDiEdge(edge);
        }
    }

    public EdgeWeightedDiGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        adj = new ArrayList<>();
        for (int i = 0; i < vertexNum; i++) {
            adj.add(new LinkedList<>());
        }
    }

    public void addEdge(DiEdge edge) {
        adj.get(edge.from()).add(edge);
        edgeNum++;
    }

    //返回与某个顶点为中心的所有的边
    //*v* 是顶点的编号
    public Iterable<DiEdge> adj(int v) {
        return adj.get(v);
    }

    public List<DiEdge> edges() {
        List<DiEdge> edges = new LinkedList<>();
        for (int i = 0; i < vertexNum; i++) {
            for (DiEdge e : adj(i)) {
                edges.add(e);
            }
        }
        return edges;
    }

    public int vertexNum() {
        return vertexNum;
    }

    public int edgeNum() {
        return edgeNum;
    }

    public Item getVertexInfo(int i) {
        return vertexInfo.get(i);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
        for (int i = 0; i < vertexNum; i++) {
            sb.append(i).append(": ").append(adj.get(i)).append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        List<String> vertexInfo = List.of("v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7");
        int[][] edges = {{4, 5}, {5, 4}, {4, 7}, {5, 7}, {7, 5}, {5, 1}, {0, 4}, {0, 2},
                {7, 3}, {1, 3}, {2, 7}, {6, 2}, {3, 6}, {6, 0}, {6, 4}};

        double[] weight = {0.35, 0.35, 0.37, 0.28, 0.28, 0.32, 0.38, 0.26, 0.39, 0.29,
                0.34, 0.40, 0.52, 0.58, 0.93};

        EdgeWeightedDiGraph<String> graph = new EdgeWeightedDiGraph<>(vertexInfo, edges, weight);

        System.out.println("该图的邻接表为\n"+graph);
        System.out.println("该图的所有边："+ graph.edges());

    }
}

Dijkstra算法的实现

import java.util.*;

public class Dijkstra {
    private DiEdge[] edgeTo;
    private double[] distTo;
    private Map<Integer, Double> minDist;

    public Dijkstra(EdgeWeightedDiGraph<?> graph, int s) {
        edgeTo = new DiEdge[graph.vertexNum()];
        distTo = new double[graph.vertexNum()];
        minDist = new HashMap<>();

        for (int i = 0; i < graph.vertexNum(); i++) {
            distTo[i] = Double.POSITIVE_INFINITY; // 1.0 / 0.0为INFINITY
        }
        // 到起点距离为0
        distTo[s] = 0.0;
        relax(graph, s);
        while (!minDist.isEmpty()) {
            relax(graph, delMin());
        }
    }

    private int delMin() {
        Set<Map.Entry<Integer, Double>> entries = minDist.entrySet();
        Map.Entry<Integer, Double> min = entries.stream().min(Comparator.comparing(Map.Entry::getValue)).get();
        int key = min.getKey();
        minDist.remove(key);
        return key;
    }

    private void relax(EdgeWeightedDiGraph<?> graph, int v) {
        for (DiEdge edge : graph.adj(v)) {
            int w = edge.to();
            if (distTo[v] + edge.weight() < distTo[w]) {
                distTo[w] = distTo[v] + edge.weight();
                edgeTo[w] = edge;
                if (minDist.containsKey(w)) {
                    minDist.replace(w, distTo[w]);
                    System.out.println(w);

                } else {
                    minDist.put(w, distTo[w]);
                }
            }
        }
    }

    public double distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        return distTo[v] != Double.POSITIVE_INFINITY;
    }

    public Iterable<DiEdge> pathTo(int v) {
        if (hasPathTo(v)) {
            LinkedList<DiEdge> path = new LinkedList<>();
            for (DiEdge edge = edgeTo[v]; edge != null; edge = edgeTo[edge.from()]) {
                path.push(edge);
            }
            return path;
        }
        return null;
    }

    public static void main(String[] args) {
        List<String> vertexInfo = List.of("v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7");
        int[][] edges = {{4, 5}, {5, 4}, {4, 7}, {5, 7}, {7, 5}, {5, 1}, {0, 4}, {0, 2},
                {7, 3}, {1, 3}, {2, 7}, {6, 2}, {3, 6}, {6, 0}, {6, 4}};

        double[] weight = {0.35, 0.35, 0.37, 0.28, 0.28, 0.32, 0.38, 0.26, 0.39, 0.29,
                0.34, 0.40, 0.52, 0.58, 0.93};

        EdgeWeightedDiGraph<String> graph = new EdgeWeightedDiGraph<String>(vertexInfo, edges, weight);
        Dijkstra dijkstra = new Dijkstra(graph, 0);
        for (int i = 0; i < graph.vertexNum(); i++) {
            System.out.print("0 to " + i + ": ");
            System.out.print("(" + dijkstra.distTo(i) + ") ");
            System.out.println(dijkstra.pathTo(i));
        }
    }
}