Wie Werte dynamisch an Dijktras-Algorithmus übergeben werden

Question

Ich versuche, den folgenden Code für Dijktras-Algorithmus zu verwenden, um das OSPF-Routing-Protokoll in Java zu implementieren. Ich möchte diesen Algorithmus dazu bringen, die Werte für die Kanten und ihre Kosten dynamisch zu übernehmen.

import java.io.*; 
import java.util.*; 

public class Dijkstra { 
    private static final Graph.Edge[] GRAPH = { 
     new Graph.Edge("a", "b", 7), 
     new Graph.Edge("a", "c", 9), 
     new Graph.Edge("a", "f", 14), 
     new Graph.Edge("b", "c", 10), 
     new Graph.Edge("b", "d", 15), 
     new Graph.Edge("c", "d", 11), 
     new Graph.Edge("c", "f", 2), 
     new Graph.Edge("d", "e", 6), 
     new Graph.Edge("e", "f", 9), 
    }; 
    private static final String START = "a"; 
    private static final String END = "e"; 

    public static void main(String[] args) { 
     Graph g = new Graph(GRAPH); 
     g.dijkstra(START); 
     g.printPath(END); 
     //g.printAllPaths(); 
    } 
} 

class Graph { 
    private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges 

    /** One edge of the graph (only used by Graph constructor) */ 
    public static class Edge { 
     public final String v1, v2; 
     public final int dist; 
     public Edge(String v1, String v2, int dist) { 
     this.v1 = v1; 
     this.v2 = v2; 
     this.dist = dist; 
     } 
    } 

    /** One vertex of the graph, complete with mappings to neighbouring vertices */ 
    public static class Vertex implements Comparable<Vertex> { 
     public final String name; 
     public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity 
     public Vertex previous = null; 
     public final Map<Vertex, Integer> neighbours = new HashMap<>(); 

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

     private void printPath() { 
     if (this == this.previous) { 
      System.out.printf("%s", this.name); 
     } else if (this.previous == null) { 
      System.out.printf("%s(unreached)", this.name); 
     } else { 
      this.previous.printPath(); 
      System.out.printf(" -> %s(%d)", this.name, this.dist); 
     } 
     } 

     public int compareTo(Vertex other) { 
     return Integer.compare(dist, other.dist); 
     } 
    } 

    /** Builds a graph from a set of edges */ 
    public Graph(Edge[] edges) { 
     graph = new HashMap<>(edges.length); 

     //one pass to find all vertices 
     for (Edge e : edges) { 
     if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); 
     if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); 
     } 

     //another pass to set neighbouring vertices 
     for (Edge e : edges) { 
     graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist); 
     //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph 
     } 
    } 

    /** Runs dijkstra using a specified source vertex */ 
    public void dijkstra(String startName) { 
     if (!graph.containsKey(startName)) { 
     System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName); 
     return; 
     } 
     final Vertex source = graph.get(startName); 
     NavigableSet<Vertex> q = new TreeSet<>(); 

     // set-up vertices 
     for (Vertex v : graph.values()) { 
     v.previous = v == source ? source : null; 
     v.dist = v == source ? 0 : Integer.MAX_VALUE; 
     q.add(v); 
     } 

     dijkstra(q); 
    } 

    /** Implementation of dijkstra's algorithm using a binary heap. */ 
    private void dijkstra(final NavigableSet<Vertex> q) {  
     Vertex u, v; 
     while (!q.isEmpty()) { 

     u = q.pollFirst(); // vertex with shortest distance (first iteration will return source) 
     if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable 

     //look at distances to each neighbour 
     for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) { 
      v = a.getKey(); //the neighbour in this iteration 

      final int alternateDist = u.dist + a.getValue(); 
      if (alternateDist < v.dist) { // shorter path to neighbour found 
       q.remove(v); 
       v.dist = alternateDist; 
       v.previous = u; 
       q.add(v); 
      } 
     } 
     } 
    } 

    /** Prints a path from the source to the specified vertex */ 
    public void printPath(String endName) { 
     if (!graph.containsKey(endName)) { 
     System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName); 
     return; 
     } 

     graph.get(endName).printPath(); 
     System.out.println(); 
    } 
    /** Prints the path from the source to every vertex (output order is not guaranteed) */ 
    public void printAllPaths() { 
     for (Vertex v : graph.values()) { 
     v.printPath(); 
     System.out.println(); 
     } 
    } 
} 

Ich habe versucht, folgende

public static void main(String[] args) { 

     Map<String, ArrayList<String>> m = new HashMap<String, ArrayList<String>>(); 

     ArrayList<String> l1 = new ArrayList<String>(); 
     l1.add("R1"); 
     l1.add("R2"); 
     l1.add("50"); 
     ArrayList<String> l2 = new ArrayList<String>(); 
     l2.add("R1"); 
     l2.add("R3"); 
     l2.add("50"); 
     ArrayList<String> l3 = new ArrayList<String>(); 
     l3.add("R4"); 
     l3.add("R3"); 
     l3.add("50"); 
     ArrayList<String> l4 = new ArrayList<String>(); 
     l4.add("R4"); 
     l4.add("R2"); 
     l4.add("50"); 

     m.put("X", l1); 
     m.put("Y", l2); 
     m.put("Z", l3); 
     m.put("W", l4); 

     System.out.println(m); 
     Graph.Edge[] GRAPH=null; 
    // private static final Graph.Edge[] GRAPH = null; 
     int i=0; 
     for(String key:m.keySet()){ 
      System.out.println(key+m.get(key).get(0)+m.get(key).get(1)+m.get(key).get(2)); 
      GRAPH[i]=new Graph.Edge(m.get(key).get(0), m.get(key).get(1),Integer.parseInt(m.get(key).get(2))); 
      i++; 
     } 
     String START = "a"; 
     String END = "e"; 
     Graph g = new Graph(GRAPH); 
     g.dijkstra(START); 
     g.printPath(END); 
     //g.printAllPaths(); 
    } 
} 

ich den Wert aus dem hashmap zum dijktras Algorithmus übergeben wollen. und initialisieren alle Kanten mit den gespeicherten Daten in der HashMap Hinweis: hashmap<LinkID,<Edge,Edge,Cost>>

Bitte vorschlagen, wo ich falsch werde oder vermuten lassen, eine bessere, die Werte vorbei dynamisch auf diese Algorithm

Answer 1

Das Beispiel verknüpfen Sie verwendet eine harte -codiertes Array

private static final Graph.Edge[] GRAPH = { 
     new Graph.Edge("a", "b", 7), 
     new Graph.Edge("a", "c", 9), 
     new Graph.Edge("a", "f", 14), 
     new Graph.Edge("b", "c", 10), 
     new Graph.Edge("b", "d", 15), 
     new Graph.Edge("c", "d", 11), 
     new Graph.Edge("c", "f", 2), 
     new Graph.Edge("d", "e", 6), 
     new Graph.Edge("e", "f", 9), 
}; 

für die Initialisierung des Diagramms. Zunächst ist es ein wenig überraschend, dass Sie scheinbar Zeichenfolgen für die Codierung der Entfernungen verwenden. Zur Konvertierung müssen Sie die Schlüssel Ihrer Map (die die Kanten aufzählen würde) durchlaufen und eine Instanz von Graph.Edege für jede Komponente erstellen, die dann sowohl mit den Eckpunktbezeichnern als auch mit der Entfernung gefüllt wird. Die Iteration über die Schlüssel Map kann in this Beispiel gefunden werden.