從源到目標節點的所有可能路徑的成本/距離

Question

在我的應用室內導航...在特定情況下....我必須找到從特定源到用戶提供的目的地的所有可能路徑。 。 Algo工作正常，並提供所有可能的路徑....但如何計算這些路徑的距離..？ 這裏是工作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

知道每個鏈路的距離。總結這些鏈接的距離。完成。

Answer 2

我修改了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")); 
    } 


}