ungerichteten Graphen für k kürzesten Wege in Dijkstra Java mit

Question

Ich versuche Dijkstra-Algorithmus zu implementieren k-kürzesten Wege in Java zu berechnen, so weit hier ist der Code ich verwende:

import java.util.List; 


public interface AbstractKShortestPathFinder<V> { 

    List<Path<V>> findShortestPaths(V source, V target, Graph<V> graph, int `k);` 

    default void checkK(int k) { 
     if (k < 1) { 
      throw new IllegalArgumentException(
        String.format("The value of k is too small: %d, should `be at least 1.", k));` 
     } 
    } 
} 

-

import java.util.*; 

import static java.util.Objects.requireNonNull; 

public class DefaultKShortestPathFinder<V> implements AbstractKShortestPathFinder<V> { 

    @Override 
    public List<Path<V>> findShortestPaths(V source, V target, Graph<V> graph, int k) { 
     requireNonNull(source, "The source node is null."); 
     requireNonNull(target, "The target node is null."); 
     requireNonNull(graph, "The graph is null."); 
     checkK(k); 

     List<Path<V>> paths = new ArrayList<>(k); 
     Map<V, Integer> countMap = new HashMap<>(); 
     Queue<Path<V>> HEAP = new PriorityQueue<>(
       Comparator.comparingDouble(Path::pathCost)); 

     HEAP.add(new Path<>(source)); 

     while (!HEAP.isEmpty() && countMap.getOrDefault(target, 0) < k) { 
      Path<V> currentPath = HEAP.remove(); 
      V endNode = currentPath.getEndNode(); 

      countMap.put(endNode, countMap.getOrDefault(endNode, 0) + 1); 

      if (endNode.equals(target)) { 
       paths.add(currentPath); 
      } 

      if (countMap.get(endNode) <= k) { 
       for (Edge<V> edge : graph.get(endNode)) { 
        Path<V> path = currentPath.append(edge); 
        HEAP.add(path); 
       } 
      } 
     } 

     return paths; 
    } 
} 

-

public class Edge<V> { 

    public final V from; 
    public final V to; 
    public final double weight; 


    public Edge(V from, V to, double weight) { 
     this.from = from; 
     this.to = to; 
     this.weight = weight; 
     if (Double.isNaN(weight)) { 
      throw new IllegalArgumentException("The weight is NaN."); 
     } 
     if (weight < 0.0) { 
      throw new IllegalArgumentException("The weight is negative."); 
     } 
    } 

} 

-

import java.util.*; 

import static java.lang.String.*; 

public class Graph<V> { 

    //could be replaced by http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Table.html 
    private Map<V,Map<V,Edge<V>>> vertexEdgeMap = new HashMap<>(); 

    @SafeVarargs 
    public Graph(Edge<V> ... edges) { 
     for (Edge<V> edge : edges) { 
      addEdge(edge); 
     } 
    } 

    private void addEdge(Edge<V> edge) { 
     vertexEdgeMap.putIfAbsent(edge.from, new HashMap<>()); 
     Map<V, Edge<V>> fromMap = vertexEdgeMap.get(edge.from); 
     if(fromMap.containsKey(edge.to)) { 
      throw new IllegalArgumentException(format("Edge between %s and %s was added twice", edge.from, edge.to)); 
     } 
     fromMap.put(edge.to, edge); 
    } 

    public Edge<V> get(V from, V to) { 
     return vertexEdgeMap.get(from).get(to); 
    } 

    public Collection<Edge<V>> get(V from) { 
     return vertexEdgeMap.getOrDefault(from, Collections.emptyMap()).values(); 
    } 

} 

-

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

import static java.lang.String.format; 

public class Path<V> { 

    private final V node; 
    private final double totalCost; 

    public Path(V source) { 
     Objects.requireNonNull(source, "The input source node is null."); 
     node = source; 
     totalCost = 0.0; 
    } 

    private Path(V node, double totalCost) { 
     this.node = node; 
     this.totalCost = totalCost; 
    } 


    public Path<V> append(Edge<V> edge) { 
     if (!node.equals(edge.from)) { 
      throw new IllegalArgumentException(format("The edge %s doesn't extend the path %s", edge, this.getNodeList())); 
     } 

     return new NonEmptyPath<>(this, edge); 
    } 

    public V getEndNode() { 
     return node; 
    } 

    public List<V> getNodeList() { 
     return new ArrayList<>(); 
    } 

    public double pathCost() { 
     return totalCost; 
    } 

    private static class NonEmptyPath<V> extends Path<V> { 
     private final Path<V> predecessor; 

     public NonEmptyPath(Path<V> path, Edge<V> edge) { 
      super(edge.to, path.totalCost + edge.weight); 
      predecessor = path; 

     } 

     @Override 
     public List<V> getNodeList() { 
      LinkedList<V> result = new LinkedList<>(); 
      Path<V> path = this; 
      while(path instanceof NonEmptyPath) { 
       result.addFirst(path.node); 
       path = ((NonEmptyPath<V>) path).predecessor; 
      } 
      result.addFirst(path.node); 
      return result; 
     } 

     @Override 
     public String toString() { 
      return getNodeList().toString(); 
     } 
    } 

} 

-

import java.util.List; 

public class Execution { 

    public static void main(String[] args) { 
     execution(); 
    } 

    private static void execution() { 

     Graph<Character> graph = new Graph<>(
       // new Edge<>('a', 'b', 5.0), 
       new Edge<>('a', 'c', 3.0), 
       new Edge<>('b', 'c', 2.0), 
       new Edge<>('b', 'd', 1.0), 
       new Edge<>('c', 'd', 3.0) 


     ); 

     List<Path<Character>> paths = new DefaultKShortestPathFinder<Character>().findShortestPaths('a', 'b', graph, 2); 



     for(Path<Character> path:paths) { 
      System.out.println('h'); 
      System.out.println(path.toString() + " cout: " + path.pathCost()); 
     } 

    } 
} 

Alles funktioniert für einen gerichteten Graphen in Ordnung, aber ich will es so modifizieren, kann es k-kürzeste Wege berechnet für ungerichteten Graphen jemand eine Idee hat wie ich das erreichen kann, weiß ich auch, dass für den gerichteten Graph in der Adjazenzmatrix [a] [b] = True, aber für [b] [a] = falsch ist.

Answer 1

Ein ungerichteter Graph ist nur ein gerichteter Graph, wo für jede Kante a -> b auch die Kante b -> a existiert. Konvertieren Sie einfach den ungerichteten Graphen in einen gerichteten Graphen und verwenden Sie Ihren bestehenden Algorithmus.