Wie man einen Graphen mit dem Algorithmus von Dijkstra darstellt, mit einer .txt-Datei als Eingabe

Question

Ich habe Probleme mit Dijkstras Algorithmus, wenn ich eine Textdatei in diesem Format bekomme.

Die erste Zeile repräsentiert die Anzahl der Scheitelpunkte. Soll ich diesen Wert als 2-dimensionalen Array speichern?

Ich dachte, dass ich den zweiten Teil des 2D-Arrays den tatsächlichen Wert haben könnte, den jeder Knoten hält.

Zum Beispiel Vertex 3 hält 78. Vertex 4 hält 87 ... etc.

Das Problem in I ausgeführt wird, die um die Kanten zu speichern. 1 4 98 Wo 1 Vertex 1 ist, 4 ist Vertex 4, und der Abstand zwischen ihnen ist 98. Wie würde ich diesen Wert von 98 speichern?

Ich bin nur hier ratlos, jeder Rat würde sehr geschätzt werden.

Unten ist der Eingang

Number of Vertexes Number of Edges Vertex NumValue Vertex Vertex NumValue

Wo, wenn es zwei Eckpunkten, die NumValue, die nach kommt, ist die Entfernung zwischen den beiden.

Eingang

5 7 3 78 4 87 5 98 1 4 98 5 4 45 1 5 140 4 3 87 2 5 150 3 5 109 3 2 73

Ausgabe

388

Answer 1

Es gibt viele Möglichkeiten, dies zu tun, sind hier einige:

public class Edge { 
    private class Node { 
     private int value; 
    } 

    private Node from, to; 
    private double distance; 
} 

Mit diesem können Sie eine Arraylist von Kanten haben das Diagramm

public class Graph { 
    private class Node { 
     private Node adjacent; 
     private double distance; 
     private int value; 
    } 

    private Node[] nodes; 
} 

Hier finden Sie eine grafische Darstellung der Klasse erstellen, um darzustellen, die eine Liste von Knoten

public class Graph { 
    private double[][] matrix; 
} 

Wiederum enthält diese ein Graph Klasse ist jedoch unter Verwendung von eine Matrix. Wenn der Knoten 1 eine Kante zu Knoten 5 mit Abstand 75,9 hat, dann matrix[1][5] == 75.9

Answer 2

Überprüfung dieser Ansatz darstellen gewichteten Graphen Kante http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/EdgeWeightedGraph.java.html