Ich habe ein Problem bei der Umwandlung von Pseudocode des Dijkstras-Algorithmus in tatsächlichen Code festgestellt. Ich wurde gegeben und Adjazenzliste wie "Standort - Nachbarstandort - Entfernung zum Standort", Beispiel für einen Knoten: AAA AAC 180 AAD 242 AAH 40. Meine Aufgabe war es, eine Datei als Adjacency-Liste wie beschrieben organisiert zu lesen, und berechnen Sie die kürzester Weg von einem Knoten zum anderen. Hier ist der Dijkstra Pseudo-Code:Dijkstra Adjazenzliste
void dijkstra(Vertex s)
{
for each Vertex v
{
v.dist = INFINITY;
v.known = false;
}
s.dist = 0;
while(there is an unknown distance vertex)
{
Vertex v = smallest unknown distance vertex;
v.known = true;
for each Vertex w adjacent to v
if(!w.known)
{
DistType cvw = cost of edge from v to w;
if(v.dist + cvw < w.dist)
{
// Update w
decrease(w.dist to v.dist + cvw);
w.path = v;
}
}
}
}
im die meisten Probleme mit der Zeile "für jeden Vertex w neben v" Hier hat mein arbeitsfreien Code:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
public class Dijkstra {
public static boolean isInteger(String s) {
return isInteger(s, 10);
}
public static boolean isInteger(String s, int radix) {
if (s.isEmpty())
return false;
for (int i = 0; i < s.length(); i++) {
if (i == 0 && s.charAt(i) == '-') {
if (s.length() == 1)
return false;
else
continue;
}
if (Character.digit(s.charAt(i), radix) < 0)
return false;
}
return true;
}
public static void dijkstra(Vertex[] a, Vertex s, int lineCount) {
int i = 0;
while (i < (lineCount)) // each Vertex v
{
a[i].dist = Integer.MAX_VALUE;
a[i].known = false;
i++;
}
s.dist = 0;
int min = Integer.MAX_VALUE; //
while (!(a[0].known == true && a[1].known == true && a[2].known == true && a[3].known == true
&& a[4].known == true && a[5].known == true && a[6].known == true && a[7].known == true
&& a[8].known == true && a[9].known == true && a[10].known == true && a[11].known == true
&& a[12].known == true)) {
System.out.println("here");
for (int b = 0; b < lineCount; b++) {
if (a[b].dist < min && a[b].known == false) {
min = a[b].dist;
}
}
int c = 0;
while (c < lineCount) {
if (a[c].dist == min && a[c].known == false) {
break;
}
c++;
}
System.out.println(min);
a[c].known = true;
int adjSize = a[c].adj.size();
int current = 0;
System.out.println(adjSize);
while (current < adjSize - 1) {
String currentAdjacent = (String) a[c].adj.get(current);
int p = 0;
while (p < lineCount) {
if (a[p].name.equals(currentAdjacent)) {
if (!a[p].known) {
String cvwString = (String) a[c].distance.get(current);
int cvw = Integer.parseInt(cvwString);
System.out.println(" This is cvw" + cvw);
System.out.println("Here2");
if (a[c].dist + cvw < a[p].dist) {
a[p].dist = a[c].dist + cvw;
a[p].path = a[c];
}
}
}
p++;
}
current++;
}
}
}
public static class Vertex {
public List adj; // Adjacency list
public List distance;
public boolean known;
public int dist; // DistType is probably int
public Vertex path;
public String name;
// Other fields and methods as needed
}
public static void printPath(Vertex v) {
if (v.path != null) {
printPath(v.path);
System.out.print(" to ");
}
System.out.print(v);
}
public static void main(String[] args) throws IOException {
int lineCounter = 0;
BufferedReader br = new BufferedReader(new FileReader("airport.txt"));
try {
StringBuilder sb = new StringBuilder();
String line = br.readLine();
while (line != null) {
sb.append(line);
sb.append(System.lineSeparator());
line = br.readLine();
lineCounter = lineCounter + 1;
}
Vertex[] arr = new Vertex[lineCounter];
for (int i = 0; i < lineCounter; i++) {
arr[i] = new Vertex();
arr[i].adj = new LinkedList<String>();
arr[i].distance = new LinkedList<Integer>();
}
;
//
int arrayCounter = 0;
String everything = sb.toString();
String[] lines = everything.split("\\s*\\r?\\n\\s*");
for (String line1 : lines) {
arr[arrayCounter] = new Vertex();
arr[arrayCounter].adj = new LinkedList<String>();
arr[arrayCounter].distance = new LinkedList<Integer>();
String[] result = line1.split("\\s+");
for (int x = 0; x < result.length; x++) {
if (x == 0) {
arr[arrayCounter].name = result[0];
continue;
} else if (isInteger(result[x])) {
arr[arrayCounter].distance.add(result[x]);
continue;
} else {
arr[arrayCounter].adj.add(result[x]);
continue;
}
}
arrayCounter++;
}
for (int i = 0; i < 12; i++) {
System.out.println(arr[i].name);
}
System.out.println(lineCounter);
dijkstra(arr, arr[3], lineCounter - 1);
printPath(arr[11]);
} finally {
br.close();
}
}
}
Mit meiner Vertex-Klasse als Wenn ich zuerst eine Reihe von while-Schleifen verwende, durchquere ich die Adjazenz-Strings, die in einer verketteten Liste gespeichert sind, während ich vergleiche, um zu sehen, welcher Scheitelpunkt der Adjazenzlisten-Zeichenkette entspricht. Gibt es eine bessere Möglichkeit zum Codieren "für jeden Vertex w neben v" mithilfe meiner Vertex-Klasse? Und ich entschuldige mich für chaotischen Code und andere Sünden, die ich vielleicht begangen habe. Vielen Dank!
Verschachtelte Strukturen ohne Einrückung machen Code fast unlesbar. Bitte beachten Sie, dass Sie die Formatierung des ersten Codeblocks korrigieren müssen. – ChiefTwoPencils
Ok, sollte jetzt besser formatiert sein. – panzerschwein
Warum implementieren Sie 'isInteger' nicht einfach mit' s.matches ("^ -? [0-9] +") '? Warum musst du das Radix beachten? (Du gibst nie irgendwas außer 10, implizit) –