JAVA/编程算法

Question

请帮我解决这个问题，我曾想过用递归算法来解决这个问题，但无法拿出解决方案。

编写一个程序，在有向无环图中找到从一个顶点到另一个顶点的最便宜路径，给定格式的数据（起始顶点、结束顶点、代价）。假设所有成本均为正。

使用数据：→ B： 1、B→ C： 1 A→ C： 2.5 A→ D： 0.4英寸→ B： 0.3

当找到从A到C的最便宜路径时，预期的答案是A=

请用Java编写解决方案，包括证明解决方案正确性的测试用例。

Answer 1

package myDijkstra;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

//Foreach node set distance[node] = HIGH
//SettledNodes = empty
//UnSettledNodes = empty
//
//Add sourceNode to UnSettledNodes
//distance[sourceNode]= 0
//
//while (UnSettledNodes is not empty) {
//  evaluationNode = getNodeWithLowestDistance(UnSettledNodes)
//  remove evaluationNode from UnSettledNodes 
//    add evaluationNode to SettledNodes
//    evaluatedNeighbors(evaluationNode)
//}
//
//getNodeWithLowestDistance(UnSettledNodes){
//  find the node with the lowest distance in UnSettledNodes and return it 
//}
//
//evaluatedNeighbors(evaluationNode){
//  Foreach destinationNode which can be reached via an edge from evaluationNode AND which is not in SettledNodes {
//    edgeDistance = getDistance(edge(evaluationNode, destinationNode))
//    newDistance = distance[evaluationNode] + edgeDistance
//    if (distance[destinationNode]  > newDistance) {
//      distance[destinationNode]  = newDistance 
//      add destinationNode to UnSettledNodes
//    }
//  }
//} 

public class Dijkstra {
    /**
     * Class define a Vertex
     * 
     * @author WEIQIANG LIANG
     *
     */
    public class Vertex {
        private String name;

        public Vertex(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "Vertex [name=" + name + "]";
        }

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

        public int hashCode() {
            return name.length();
        }

    }

    /**
     * Class define path(known from the question)
     * 
     * @author WEIQIANG LIANG
     *
     */
    public class Path {
        private Vertex source;
        private Vertex destination;
        private double cost;

        public Path(Vertex source, Vertex destination, double d) {
            super();
            this.source = source;
            this.destination = destination;
            this.cost = d;
        }

        public Vertex getSource() {
            return source;
        }

        public void setSource(Vertex source) {
            this.source = source;
        }

        public Vertex getDestination() {
            return destination;
        }

        public void setDestination(Vertex destination) {
            this.destination = destination;
        }

        public double getCost() {
            return cost;
        }

        public void setCost(double cost) {
            this.cost = cost;
        }

        @Override
        public String toString() {
            return "Path [source=" + source.name + ", destination="
                    + destination.name + ", cost=" + cost + "]";
        }

    }

    // storage for each nodes
    private static List<Dijkstra.Vertex> verties = new ArrayList<>();
    // storage for provided path
    private static List<Dijkstra.Path> path = new ArrayList<>();
    // storage for shortest distance from source nodes to each destination nodes
    private static Map<Dijkstra.Vertex, Double> distance = new HashMap<>();
    // storage for nodes that already visited
    private static Set<Vertex> settledNodes = new HashSet<>();
    // storage for nodes that already unvisited
    private static Set<Vertex> unSettledNodes = new HashSet<>();
    private static double INFINITY_VALUE = 9999.99;

    static {
        // pre-setup
        Vertex A = new Dijkstra().new Vertex("A");
        Vertex B = new Dijkstra().new Vertex("B");
        Vertex C = new Dijkstra().new Vertex("C");
        Vertex D = new Dijkstra().new Vertex("D");
        verties.add(A);
        verties.add(B);
        verties.add(C);
        verties.add(D);
        // known path
        Path AB = new Dijkstra().new Path(A, B, 1.0);
        Path AC = new Dijkstra().new Path(A, C, 2.5);
        Path AD = new Dijkstra().new Path(A, D, 0.4);
        Path BC = new Dijkstra().new Path(B, C, 1.0);
        Path BD = new Dijkstra().new Path(D, B, 0.3);
        path.add(AB);
        path.add(AC);
        path.add(AD);
        path.add(BC);
        path.add(BD);
        System.out.println("Verteies: " + verties);
        System.out.println("Path: " + path);
    }

    public static void main(String args[]) {
        Vertex source = new Dijkstra().new Vertex("A");
        Vertex target = new Dijkstra().new Vertex("C");
        excute(source);
        System.out.println(Dijkstra.distance.get(target));
    }

    /**
     * Main Compute function
     * 
     * @param source
     *            - the start/source nodes
     */
    private static void excute(Vertex source) {
        // 1.we put the source to our shortest distance map as distination node,
        // and mark cost = 0
        Dijkstra.distance.put(source, new Double(0));
        // 2.we put the source to our unsettled/unvisited map
        Dijkstra.unSettledNodes.add(source);
        // 3.loop though unsettled/unvisited nodes until is empty
        while (!Dijkstra.unSettledNodes.isEmpty()) {
            //4.get the shortest/smallest cost from the source node to target node.
            Dijkstra.Vertex vertex = Dijkstra
                    .getminimumVertex(Dijkstra.unSettledNodes);
            Dijkstra.settledNodes.add(vertex);
            Dijkstra.unSettledNodes.remove(vertex);
            findMinimalDistance(vertex);
        }
    }

    /**
     * 
     * @param source
     */
    private static void findMinimalDistance(Vertex source) {
        // 1.find all the relative(connected) neighbors nodes in the known path
        List<Vertex> adjanceNodes = getNeighbors(source);
        for (Vertex target : adjanceNodes) {
            // 2. calculate if the known shortest cost greater than the computed
            // cost
            // which is the source node -> current node, and the current node ->
            // target node
            if (getShortestPath(target) > getShortestPath(source)
                    + getDistanceByPath(source, target)) {
                // 3.update our distance object
                Dijkstra.distance.put(target, getShortestPath(source)
                        + getDistanceByPath(source, target));
                // 4.add unknown nodes to search
                Dijkstra.unSettledNodes.add(target);
            }
        }
    }

    /**
     * Get path cost from the known path route
     * 
     * @param source
     *            - source of the path route
     * @param target
     *            - distination of the path route
     * @return - the cost of this (source,destination) path route.
     */
    private static double getDistanceByPath(Vertex source, Vertex target) {
        for (Path pathRoute : path) {
            if (pathRoute.getSource().equals(source)
                    && pathRoute.getDestination().equals(target)) {
                return pathRoute.getCost();
            }
        }
        throw new RuntimeException("Should not happen");
    }

    /**
     * Get all relative nodes from the path by providing source nodes
     * 
     * @param vertex
     *            - source nodes
     * @return - a list of relative destination nodes from the path.
     */
    private static List<Vertex> getNeighbors(Vertex vertex) {
        List<Vertex> neighbors = new ArrayList<>();
        for (Path pathRoute : path) {
            if (pathRoute.getSource().equals(vertex) && !Dijkstra.settledNodes
                    .contains(pathRoute.getDestination())) {
                neighbors.add(pathRoute.getDestination());
            }
        }
        return neighbors;
    }

    /**
     * @param unSettledNodes
     * @return
     */
    private static Vertex getminimumVertex(Set<Vertex> unSettledNodes) {
        Dijkstra.Vertex minimum = null;
        for (Vertex vertex : unSettledNodes) {
            if (minimum == null) {
                minimum = vertex;
            } else {
                if (getShortestPath(minimum) > getShortestPath(vertex)) {
                    minimum = vertex;
                }
            }
        }
        return minimum;
    }

    /**
     * find minimum cost from source to provided target vertex from known
     * distance if the target vertex is known, we set the cost to INFINITY_VALUE
     * and added to known distance, otherwise retrieve stored cost from known
     * distance.
     * 
     * @param target
     *            - the target vertex.
     * @return - the known distance cost if we known the target, otherwise we
     *         return INFINITY_VALUE
     */
    private static double getShortestPath(Vertex target) {
        // we tried to find if we known this target vertex and its cost,
        // otherwise we should add the target vertex and
        // set it to inifinity value.

        if (Dijkstra.distance == null || Dijkstra.distance.isEmpty()) {
            throw new RuntimeException("distance object should not be empty");
        }

        Double knownCost = Dijkstra.distance.get(target);
        if (knownCost == null) {
            Dijkstra.distance.put(target, INFINITY_VALUE);
            return INFINITY_VALUE;
        }
        // otherwise we return the known distance
        return knownCost.doubleValue();
    }
}