Dijkstra邻接表
Dijkstra adjacency list
我 运行 遇到了将 Dijkstras 算法的伪代码转换为实际代码的问题。我得到了邻接列表,例如一个节点的 "Location - adjacent location - distance to location," 示例:AAA AAC 180 AAD 242 AAH 40。
我的任务是读取一个按照描述的邻接表组织的文件,并计算从一个节点到另一个节点的最短路径。
这是 Dijkstra 伪代码:
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;
}
}
}
}
我最麻烦的是 "for each Vertex w adjacent to v"
这是我的非工作代码:
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();
}
}
}
按原样使用我的顶点 class 我使用一系列 while 循环首先遍历存储在链表中的邻接字符串,同时比较以查看哪个顶点等同于邻接列表字符串。有没有更好的方法来使用我的 Vertex class 来编码 "for each Vertex w adjacent to v"?并为混乱的代码和我可能犯下的任何其他风格的错误提前道歉。谢谢!
要解决此问题,您需要一堆 "Node" 对象,存储在 HashMap 中,以源位置为键。
在节点中,您需要一组对相邻 "Node" 对象(或至少它们的 "key" 的引用的集合,以便您可以针对它编写逻辑。"Node" 还需要知道它的位置和到每个 "adjacent" 节点的距离。想想伦敦地铁地图 - 每个车站至少连接到一个其他车站。通常两个或更多。因此,地铁站的相邻节点是您可以到达的下一站从那个站。
一旦有了该数据结构,就可以使用递归例程遍历每个单独的节点。然后它应该遍历每个子节点(又名相邻节点),并通过将此数据存储在 HashMap 中并在递归时使用当前累积距离来跟踪从初始(源)节点到当前节点的距离(或 "walking"图表”)。此跟踪信息应该是递归时方法签名的一部分。您还需要跟踪递归时所采用的当前路径,以避免循环(最终会讽刺地导致 WhosebugError)。你可以使用HashSet来做到这一点。这个Set应该跟踪源和当前节点的位置作为入口键。如果你在递归过程中看到这个存在,那么你已经看到它了,所以不要继续处理。
我不会为您编写解决方案,因为我怀疑您在理解答案的过程中会问更具体的问题,而这些问题很可能在其他地方得到解答。
我 运行 遇到了将 Dijkstras 算法的伪代码转换为实际代码的问题。我得到了邻接列表,例如一个节点的 "Location - adjacent location - distance to location," 示例:AAA AAC 180 AAD 242 AAH 40。 我的任务是读取一个按照描述的邻接表组织的文件,并计算从一个节点到另一个节点的最短路径。 这是 Dijkstra 伪代码:
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;
}
}
}
}
我最麻烦的是 "for each Vertex w adjacent to v" 这是我的非工作代码:
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();
}
}
}
按原样使用我的顶点 class 我使用一系列 while 循环首先遍历存储在链表中的邻接字符串,同时比较以查看哪个顶点等同于邻接列表字符串。有没有更好的方法来使用我的 Vertex class 来编码 "for each Vertex w adjacent to v"?并为混乱的代码和我可能犯下的任何其他风格的错误提前道歉。谢谢!
要解决此问题,您需要一堆 "Node" 对象,存储在 HashMap 中,以源位置为键。
在节点中,您需要一组对相邻 "Node" 对象(或至少它们的 "key" 的引用的集合,以便您可以针对它编写逻辑。"Node" 还需要知道它的位置和到每个 "adjacent" 节点的距离。想想伦敦地铁地图 - 每个车站至少连接到一个其他车站。通常两个或更多。因此,地铁站的相邻节点是您可以到达的下一站从那个站。
一旦有了该数据结构,就可以使用递归例程遍历每个单独的节点。然后它应该遍历每个子节点(又名相邻节点),并通过将此数据存储在 HashMap 中并在递归时使用当前累积距离来跟踪从初始(源)节点到当前节点的距离(或 "walking"图表”)。此跟踪信息应该是递归时方法签名的一部分。您还需要跟踪递归时所采用的当前路径,以避免循环(最终会讽刺地导致 WhosebugError)。你可以使用HashSet来做到这一点。这个Set应该跟踪源和当前节点的位置作为入口键。如果你在递归过程中看到这个存在,那么你已经看到它了,所以不要继续处理。
我不会为您编写解决方案,因为我怀疑您在理解答案的过程中会问更具体的问题,而这些问题很可能在其他地方得到解答。