Algoritmo dijkstra per array 2D in Java

Question

Questo è per un progetto scolastico; Mi sto imbattendo in un'enorme quantità di problemi e non riesco a trovare una soluzione comprensibile.

a b c d e z 
a - 2 3 - - - 
b 2 - - 5 2 - 
c 3 - - - 5 - 
d - 5 - - 1 2 
e - 2 5 1 - 4 
z - - - 2 4 - 

Questa è la matrice bidimensionale. Quindi se vuoi trovare il percorso più breve, da a, b, e, d, z = 7, e (a, b) = (b, a) - ti porta alla nuova riga a per la riga adiacente percorsi

C'è qualcuno che può aiutarmi ad implementare l'algoritmo di Dijkstra per questo esempio? Lo apprezzerei davvero. (Mi piacciono molto gli array, le mappe e i set mi confondono un po ', le liste sono gestibili - anche se sono disposto a cercare qualsiasi soluzione a questo punto)

[Almeno non sto solo strappando via una fonte dalla rete. Io in realtà voglio imparare queste cose ... E 'solo molto difficile (>. <)]

Oh, avviare punto è A e il punto end Z

---

Come la maggior parte delle persone, non trovo il concetto dell'algoritmo è difficile - posso solo vedere come ottenere la codifica giusta ... Aiuto per favore?

Codice di esempio: un amico mi ha aiutato molto (anche se è pieno di strutture di dati che trovo difficili da seguire) Ho anche provato ad adattare il codice C++ da dreamincode.net/forums/blog/martyr2/ index.php? showentry = 578 in Java, ma che non è andato così bene ...

import java.util.*; 

public class Pathy{ 

    private static class pathyNode{ 
     public final String name; 
     public Map<pathyNode, Integer> adjacentNodes; 

     public pathyNode(String n){ 
      name = n; 
      adjacentNodes = new HashMap<pathyNode, Integer>(); 
     } 

    } 

    //instance variables 

    //constructors 

    //accessors 

    //methods 
    public static ArrayList<pathyNode> convert(int[][] inMatrix){ 
     ArrayList<pathyNode> nodeList = new ArrayList<pathyNode>(); 
     for(int i = 0; i < inMatrix.length; i++){ 
      nodeList.add(new pathyNode("" + i)); 
     } 
     for(int i = 0; i < inMatrix.length; i++){ 
      for(int j = 0; j < inMatrix[i].length; j++){ 
       if(inMatrix[i][j] != -1){ 
        nodeList.get(i).adjacentNodes.put(nodeList.get(j), 
          new Integer(inMatrix[i][j])); 
       } 
      } 
     } 
     return nodeList; 
    } 

    public static Map<pathyNode, Integer> Dijkstra(ArrayList<pathyNode> inGraph){ 
     Set<pathyNode> visited = new HashSet<pathyNode>(); 
     visited.add(inGraph.get(0)); 
     pathyNode source = inGraph.get(0); 
     Map answer = new TreeMap<pathyNode, Integer>(); 
     for(pathyNode node : inGraph){ 
      dijkstraHelper(visited, 0, source, node); 
      answer.put(node, dijkstraHelper(visited, 0, source, node)); 
     } 
     return answer; 
    } 

    private static int dijkstraHelper(Set<pathyNode> visited, int sum, pathyNode start, pathyNode destination){ 
     Map<pathyNode, Integer> adjacent = new HashMap<pathyNode, Integer>(); 

     for(pathyNode n : visited){ 
      for(pathyNode m: n.adjacentNodes.keySet()){ 
       if(adjacent.containsKey(m)){ 
        Integer temp = n.adjacentNodes.get(m); 
        if(temp < adjacent.get(m)){ 
         adjacent.put(m, temp); 
        } 
       } 
       else{ 
        adjacent.put(m, n.adjacentNodes.get(m)); 
       } 
      } 
     } 

     Map<pathyNode, Integer> adjacent2 = new HashMap<pathyNode, Integer>(); 
     Set<pathyNode> tempSet = adjacent.keySet(); 
     tempSet.removeAll(visited); 
     for(pathyNode n: tempSet){ 
      adjacent2.put(n, adjacent.get(n)); 
     } 
     adjacent = adjacent2; 
     Integer min = new Integer(java.lang.Integer.MAX_VALUE); 
     pathyNode minNode = null; 

     for(pathyNode n: adjacent.keySet()){ 
      Integer temp = adjacent.get(n); 
      if(temp < min){ 
       min = temp; 
       minNode = n; 
      } 
     } 
     visited.add(minNode); 
     sum += min.intValue(); 
     sum = dijkstraHelper(visited, sum, start, destination); 
     return sum; 
    } 

    //main 
    public static void main(String[] args){ 

     int[][] input = new int[][] { {-1, 2, 3, -1, -1, -1}, 
          {2, -1, -1, 5, 2, -1}, 
          {3, -1, -1, -1, 5, -1}, 
          {-1, 5, -1, -1, 1, 2}, 
          {-1, 2, 5, 1, -1, 4}, 
          {-1, -1, -1, 2, 4, -1}, 
         }; 
         //-1 represents an non-existant path 

     System.out.println(Dijkstra(convert(input))); 
    } 
} 

Answer 1

la rappresentazione che si sta chiamando matrice 2D, è la rappresentazione matrice di adiacenza di un grafo e il problema si è il tentativo di risolvere è un'istanza del problema "Single-Source Shortest Paths": l'algoritmo di Dijkstra è progettato per risolvere questo tipo di problema, potrebbe essere utile http://renaud.waldura.com/doc/java/dijkstra/. Scaricare il codice dal sito e leggere la documentazione. Ed a scrivere codice simile al seguente

RoutesMap map = map = new DenseRoutesMap(5); 
    map.addDirectRoute(City.A, City.B, 2); 
    map.addDirectRoute(City.A, City.C, 3); 
    map.addDirectRoute(City.B, City.A, 2); 
    map.addDirectRoute(City.B, City.D, 5); 
    map.addDirectRoute(City.B, City.D, 2); 
    ... 
    DijkstraEngine engine = new DijkstraEngine(map); 
    int distance = engine.getShortestDistance(City.F); 

Answer 2

Non sapere se qualcuno è ancora interessato a questa rappresentazione matrice Dijikstra ma ho pensato a codifica Dijikstra in Actionscript e così prima ho dovuto insegnare a me stesso come Dijuikstra funzionato. Avendolo fatto e cercando di codificarlo, ho realizzato solo la scorsa notte che potevo rappresentare i nodi e le distanze in una matrice come quella che hai in cima a questo post. La mia teoria è allora che trovare il percorso più breve sarà una questione molto semplice. Sto ancora facendo esperimenti per assicurarmi di correggere.

Nella matrice;

abcdez a - 2 3 - - - b 2 - - 5 2 - c 3 - - - 5 - d - 5 - - 1 2 e - 2 5 1 - 4 z - - - 2 4 -

Inizio a guardare la riga "a" (poiché questo è il punto di partenza) e selezionare il numero più piccolo nella riga 2 (sotto b). Quindi scrivo il percorso come "a-b" al costo di 2. Quindi vado alla riga b e di nuovo trovo il numero più piccolo a DESTRA di b (dato che siamo già al nodo B. Questo mi dà 2 sotto la "e". Quindi il percorso è ora "a - b - e" ad un costo totale di 4. i Poi guarda la riga "e" e la regola dovrebbe trovare il numero più piccolo che appare dopo la colonna "e". Questo mi darebbe "z" e darebbe il percorso completo come "a-b-e-z" e un costo totale di 8. Tuttavia, e ricordo che l'ho capito solo ieri sera, la metodologia deve riconoscere che mentre osservo la riga "e" un'altra possibilità è quella di andare alla colonna d al costo di 1.Poi guarda la riga d per il numero più basso dopo la riga d che mi darà la riga "z" al costo di 2.

Quindi questa è una soluzione migliore con il percorso "a - b - e - d -z "al costo totale di 7 come hai detto correttamente.

OK Ho ancora bisogno di codificare questo in Actionscript ma il mio istinto è che sarà molto facile codificare in Actionscript. Paura di non avere esperienza in Java, ma se sei d'accordo con il mio metodo dovrebbe essere facile codificarlo in Java.

Paul