java成本/从源节点到目标节点的所有可能路径的距离

Question

在我的应用程序室内导航。。。在特定情况下。。。。我必须找到从特定来源到用户提供的目的地的所有可能路径。。。 Algo工作正常，给出了所有可能的路径。。。。但是如何计算这些路径的距离呢。。？？？ 这是工作算法

class GraphFindAllPaths<T> implements Iterable<T> {

/* A map from nodes in the graph to sets of outgoing edges.  Each
 * set of edges is represented by a map from edges to doubles.
 */
public final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();

/**
 *  Adds a new node to the graph. If the node already exists then its a
 *  no-op.
 * 
 * @param node  Adds to a graph. If node is null then this is a no-op.
 * @return      true if node is added, false otherwise.
 */


public boolean addNode(T node) {
    if (node == null) {
        throw new NullPointerException("The input node cannot be null.");
    }
    if (graph.containsKey(node)) return false;

    graph.put(node, new HashMap<T, Double>());
    return true;
}

/**
 * Given the source and destination node it would add an arc from source 
 * to destination node. If an arc already exists then the value would be 
 * updated the new value.
 *  
 * @param source                    the source node.
 * @param destination               the destination node.
 * @param length                    if length if 
 * @throws NullPointerException     if source or destination is null.
 * @throws NoSuchElementException   if either source of destination does not exists. 
 */
public void addEdge (T source, T destination, double length) {
    if (source == null || destination == null) {
        throw new NullPointerException("Source and Destination, both should be non-null.");
    }
    if (!graph.containsKey(source) || !graph.containsKey(destination)) {
        throw new NoSuchElementException("Source and Destination, both should be part of graph");
    }
    /* A node would always be added so no point returning true or false */
    graph.get(source).put(destination, length);



}

/**
 * Removes an edge from the graph.
 * 
 * @param source        If the source node.
 * @param destination   If the destination node.
 * @throws NullPointerException     if either source or destination specified is null
 * @throws NoSuchElementException   if graph does not contain either source or destination
 */
public void removeEdge (T source, T destination) {
    if (source == null || destination == null) {
        throw new NullPointerException("Source and Destination, both should be non-null.");
    }
    if (!graph.containsKey(source) || !graph.containsKey(destination)) {
        throw new NoSuchElementException("Source and Destination, both should be part of graph");
    }
    graph.get(source).remove(destination);
}

/**
 * Given a node, returns the edges going outward that node,
 * as an immutable map.
 * 
 * @param node The node whose edges should be queried.
 * @return An immutable view of the edges leaving that node.
 * @throws NullPointerException   If input node is null.
 * @throws NoSuchElementException If node is not in graph.
 */
public Map<T, Double> edgesFrom(T node) {
    if (node == null) {
        throw new NullPointerException("The node should not be null.");
    }
    Map<T, Double> edges = graph.get(node);
    if (edges == null) {
        throw new NoSuchElementException("Source node does not exist.");
    }
    return Collections.unmodifiableMap(edges);
}

/**
 * Returns the iterator that travels the nodes of a graph.
 * 
 * @return an iterator that travels the nodes of a graph.
 */
@Override public Iterator<T> iterator() {
    //System.out.println(graph.keySet().iterator());
    return graph.keySet().iterator();
}
}

/**
 * Given a connected directed graph, find all paths between any two input points.
 */
public class FindAllPaths<T> {

private final  GraphFindAllPaths<T> graph;

/**
 * Takes in a graph. This graph should not be changed by the client
 */
public FindAllPaths(GraphFindAllPaths<T> graph) {
    if (graph == null) {
        throw new NullPointerException("The input graph cannot be null.");
    }
    this.graph = graph;
}


private void validate (T source, T destination) {

    if (source == null) {
        throw new NullPointerException("The source: " + source + " cannot be  null.");
    }
    if (destination == null) {
        throw new NullPointerException("The destination: " + destination + " cannot be  null.");
    }
    if (source.equals(destination)) {
        throw new IllegalArgumentException("The source and destination: " + source + " cannot be the same.");
    }
}

/**
 * Returns the list of paths, where path itself is a list of nodes.
 * 
 * @param source            the source node
 * @param destination       the destination node
 * @return                  List of all paths
 */
public List<List<T>> getAllPaths(T source, T destination) {
    validate(source, destination);

    List<List<T>> paths = new ArrayList<List<T>>();
    recursive(source, destination, paths, new LinkedHashSet<T>());
    return paths;
}


// so far this dude ignore's cycles.
private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path) {
    path.add(current);

    if (current == destination) {
        paths.add(new ArrayList<T>(path));
        path.remove(current);
        return;
    }

    final Set<T> edges  = graph.edgesFrom(current).keySet();

    for (T t : edges) {
        if (!path.contains(t)) {
            //System.out.println(t);
            recursive (t, destination, paths, path);
        }
    }

    path.remove(current);
}    

public static void main(String[] args) {
    GraphFindAllPaths<String> graphFindAllPaths = new GraphFindAllPaths<String>();
    graphFindAllPaths.addNode("A");
    graphFindAllPaths.addNode("B");
    graphFindAllPaths.addNode("C");
    graphFindAllPaths.addNode("D");

    graphFindAllPaths.addEdge("A", "B", 10);
    graphFindAllPaths.addEdge("A", "C", 15);
    graphFindAllPaths.addEdge("B", "A", 10);
    graphFindAllPaths.addEdge("C", "A", 15);
    graphFindAllPaths.addEdge("B", "D", 10);
    graphFindAllPaths.addEdge("C", "D", 20);
    graphFindAllPaths.addEdge("D", "B", 10);
    graphFindAllPaths.addEdge("D", "C", 20);

    graphFindAllPaths.addEdge("B", "C", 5);
    graphFindAllPaths.addEdge("C", "B", 5);



    FindAllPaths<String> findAllPaths = new FindAllPaths<String>(graphFindAllPaths);



    for (List<String> path :findAllPaths.getAllPaths("D", "A"))
    {
        System.out.println(path);
    }


   // assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
}


}

代码打印所有可能的路径

[D, B, A]
[D, B, C, A]
[D, C, A]
[D, C, B, A]

Answer 1

我修改了Maryea提供的代码，以显示每条路径的总成本/距离

package com.mini.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Set;

class GraphFindAllPaths<T> implements Iterable<T> {

    /* A map from nodes in the graph to sets of outgoing edges.  Each
     * set of edges is represented by a map from edges to doubles.
     */
    public final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();

    /**
     *  Adds a new node to the graph. If the node already exists then its a
     *  no-op.
     * 
     * @param node  Adds to a graph. If node is null then this is a no-op.
     * @return      true if node is added, false otherwise.
     */


    public boolean addNode(T node) {
        if (node == null) {
            throw new NullPointerException("The input node cannot be null.");
        }
        if (graph.containsKey(node)) return false;

        graph.put(node, new HashMap<T, Double>());
        return true;
    }

    /**
     * Given the source and destination node it would add an arc from source 
     * to destination node. If an arc already exists then the value would be 
     * updated the new value.
     *  
     * @param source                    the source node.
     * @param destination               the destination node.
     * @param length                    if length if 
     * @throws NullPointerException     if source or destination is null.
     * @throws NoSuchElementException   if either source of destination does not exists. 
     */
    public void addEdge (T source, T destination, double length) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        /* A node would always be added so no point returning true or false */
        graph.get(source).put(destination, length);



    }

    /**
     * Removes an edge from the graph.
     * 
     * @param source        If the source node.
     * @param destination   If the destination node.
     * @throws NullPointerException     if either source or destination specified is null
     * @throws NoSuchElementException   if graph does not contain either source or destination
     */
    public void removeEdge (T source, T destination) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        graph.get(source).remove(destination);
    }

    /**
     * Given a node, returns the edges going outward that node,
     * as an immutable map.
     * 
     * @param node The node whose edges should be queried.
     * @return An immutable view of the edges leaving that node.
     * @throws NullPointerException   If input node is null.
     * @throws NoSuchElementException If node is not in graph.
     */
    public Map<T, Double> edgesFrom(T node) {
        if (node == null) {
            throw new NullPointerException("The node should not be null.");
        }
        Map<T, Double> edges = graph.get(node);
        if (edges == null) {
            throw new NoSuchElementException("Source node does not exist.");
        }
        return Collections.unmodifiableMap(edges);
    }


    /**
     * Returns the iterator that travels the nodes of a graph.
     * 
     * @return an iterator that travels the nodes of a graph.
     */
    @Override public Iterator<T> iterator() {
        //System.out.println(graph.keySet().iterator());
        return graph.keySet().iterator();
    }
}

/**
 * Given a connected directed graph, find all paths between any two input points.
 */
public class FindAllPaths<T> {

    private final  GraphFindAllPaths<T> graph;

    /**
     * Takes in a graph. This graph should not be changed by the client
     */
    public FindAllPaths(GraphFindAllPaths<T> graph) {
        if (graph == null) {
            throw new NullPointerException("The input graph cannot be null.");
        }
        this.graph = graph;
    }


    private void validate (T source, T destination) {

        if (source == null) {
            throw new NullPointerException("The source: " + source + " cannot be  null.");
        }
        if (destination == null) {
            throw new NullPointerException("The destination: " + destination + " cannot be  null.");
        }
        if (source.equals(destination)) {
            throw new IllegalArgumentException("The source and destination: " + source + " cannot be the same.");
        }
    }

    /**
     * Returns the list of paths, where path itself is a list of nodes.
     * 
     * @param source            the source node
     * @param destination       the destination node
     * @return                  List of all paths
     */
    public List<List<T>> getAllPaths(T source, T destination) {
        validate(source, destination);
        Map<List<T>,Double> pathWithCost = new HashMap<List<T>,Double>();

        List<List<T>> paths = new ArrayList<List<T>>();
        List<Double> totalCost = new ArrayList<Double>();
        Double cost = new Double(0);
        recursive(source, destination, paths, new LinkedHashSet<T>(),totalCost,cost, new HashMap<T, Double>());
        for(int i=0;i<paths.size();i++){
            pathWithCost.put(paths.get(i), totalCost.get(i));
        }
        return paths;
    }

    // so far this dude ignore's cycles.
    private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path, List<Double> totalCost,Double cost, Map<T, Double> allEdges) {
        path.add(current);
        if(allEdges.get(current)!=null){
            cost= cost+allEdges.get(current);
        }
        if (current == destination) {
            cost= cost+allEdges.get(current);
            paths.add(new ArrayList<T>(path));

            cost= cost-allEdges.get(current);
            totalCost.add(cost);
            path.remove(current);
            return;
        }

        allEdges = graph.edgesFrom(current);

        final Set<T> edges  = graph.edgesFrom(current).keySet();

        for (T t : edges) {
            if (!path.contains(t)) {
                //System.out.println(t);
                recursive (t, destination, paths, path,totalCost,cost , allEdges);
            }
        }

        path.remove(current);
    }    


    /**
     * Returns the list of paths, where path itself is a list of nodes.
     * 
     * @param source            the source node
     * @param destination       the destination node
     * @return                  List of all paths
     */
    public  Map<List<T>,Double> getAllPathsWithCost(T source, T destination) {
        validate(source, destination);
        Map<List<T>,Double> pathWithCost = new HashMap<List<T>,Double>();

        List<List<T>> paths = new ArrayList<List<T>>();
        List<Double> totalCost = new ArrayList<Double>();
        Double cost = new Double(0);
        recursiveWithCost(source, destination, paths, new LinkedHashSet<T>(),totalCost,cost, new HashMap<T, Double>());
        for(int i=0;i<paths.size();i++){
            pathWithCost.put(paths.get(i), totalCost.get(i));
        }
        return pathWithCost;
    }

    // so far this dude ignore's cycles.
    private void recursiveWithCost (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path, List<Double> totalCost,Double cost, Map<T, Double> allEdges) {
        path.add(current);
        if(allEdges.get(current)!=null){
            cost= cost+allEdges.get(current);
        }
        if (current == destination) {
            cost= cost+allEdges.get(current);
            paths.add(new ArrayList<T>(path));

            cost= cost-allEdges.get(current);
            totalCost.add(cost);
            path.remove(current);
            return;
        }

        allEdges = graph.edgesFrom(current);

        final Set<T> edges  = graph.edgesFrom(current).keySet();

        for (T t : edges) {
            if (!path.contains(t)) {
                //System.out.println(t);
                recursiveWithCost (t, destination, paths, path,totalCost,cost , allEdges);
            }
        }

        path.remove(current);
    }    


    public static void main(String[] args) {
        GraphFindAllPaths<String> graphFindAllPaths = new GraphFindAllPaths<String>();
        graphFindAllPaths.addNode("A");
        graphFindAllPaths.addNode("B");
        graphFindAllPaths.addNode("C");
        graphFindAllPaths.addNode("D");

        graphFindAllPaths.addEdge("A", "B", 10);
        graphFindAllPaths.addEdge("A", "C", 15);
        graphFindAllPaths.addEdge("B", "A", 10);
        graphFindAllPaths.addEdge("C", "A", 15);
        graphFindAllPaths.addEdge("B", "D", 10);
        graphFindAllPaths.addEdge("C", "D", 20);
        graphFindAllPaths.addEdge("D", "B", 10);
        graphFindAllPaths.addEdge("D", "C", 20);

        graphFindAllPaths.addEdge("B", "C", 5);
        graphFindAllPaths.addEdge("C", "B", 5);



        FindAllPaths<String> findAllPaths = new FindAllPaths<String>(graphFindAllPaths);

        System.out.println("All possible Paths : ");
        for (List<String> path :findAllPaths.getAllPaths("D", "A"))
        {
            System.out.println(path);
        }

        System.out.println("\nAll possible paths with total distance : ");
        Map<List<String>,Double> pathWithCost = findAllPaths.getAllPathsWithCost("D", "A");
        for(Entry<List<String>, Double> s : pathWithCost.entrySet()){
            System.out.println(s);
        }

        // assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
    }


}

Answer 2

知道每个环节的距离。将这些链接上的距离相加。完成了