最短路径之迪杰斯特拉算法

CSDN

package com.zhang.reflection.面试.算法模版.图.最短路径;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
/**
 * 表示图：邻接表、邻接矩阵
 * 没有权值为负数的边，单元最短路径，一定规定出发点，计算出该点到其他点的最短路径
 */
public class 迪杰斯特拉 {
    //图
    static class Graph{
        //点集<编号，实际的点>
        public HashMap<Integer,Node> nodes;
        //边集
        public HashSet<Edge> edges;
        public Graph(){
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }
    //点
    static class Node{
        //点上的值
        public int value;
        //点的入度
        public int in;
        //点的出度
        public int out;
        //相邻节点集,以该节点为起点
        public ArrayList<Node> nexts;
        //相邻边集，以该节点为起点
        public ArrayList<Edge> edges;
        public Node(int value){
            this.value=value;
            in=0;
            out=0;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }
    //边
    static class Edge{
        //边得权值
        public int weight;
        //边的起点
        public Node from;
        //边的终点
        public Node to;
        public Edge(int weight,Node from,Node to){
            this.weight=weight;
            this.from=from;
            this.to=to;
        }
    }
    //根据矩阵创建出图
    //matrix二维矩阵:matrix[i][0]表示起点,matrix[i][1]表示终点,matrix[i][2]表示权值;
    public static Graph createGraph(Integer[][] matrix){
        Graph graph=new Graph();
        for(int i=0;i<matrix.length;i++){
            Integer from=matrix[i][0];
            Integer to=matrix[i][1];
            Integer weight=matrix[i][2];
            if(!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if(!graph.nodes.containsKey(to)){
                graph.nodes.put(to,new Node(to));
            }
            Node fromNode=graph.nodes.get(from);
            Node toNode=graph.nodes.get(to);
            Edge newEdge=new Edge(weight,fromNode,toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
    //狄杰斯特拉，node为出发点
    public static HashMap<Node, Integer> dijestral(Node head) {
        //源头到当前点的距离即head到node的最小距离
        HashMap<Node, Integer> minDistance = new HashMap<>();
        //最开始head到自己的的距离就是0
        minDistance.put(head, 0);
        //记录已经用过的节点
        HashSet<Node> selectNode = new HashSet<>();
        //找到一个在minDistance中最小的记录，但不在selectNode中的节点找出来使用
        Node minNode = getMinDistanceAndUnselectedNode(minDistance, selectNode);
        while (minNode != null) {
            int diatance = minDistance.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!selectNode.contains(toNode)) {
                    minDistance.put(toNode, diatance + edge.weight);
                }else {
                    minDistance.put(toNode, Math.min(minDistance.get(toNode), diatance + edge.weight));
                }
            }
            selectNode.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(minDistance, selectNode);
        }
        return minDistance;
    }
    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
}