문제 설명
무방향 그래프에서 노드에 대한 최단 경로 찾기 (Finding the shortest path to a node in an undirected graph)
그래서 누군가가 해결해 주기를 바라는 마음으로 내 질문을 게시하기보다는 다음에 해야 할 일에 대한 통찰력을 얻고 싶습니다. 하여튼 상황은 이러합니다. 다음 형식의 정수 집합이 있습니다.
11 3 2 3 0 3 x x xx
이 정수는 다음과 같이 표시됩니다. 여기서 11은 3, 2는 3 등으로 연결됩니다. 내 목표는 알고리즘 수단을 사용하여 0번 지점에서 1번 지점까지 도달하는 방법을 보여주는 경로를 만드는 것입니다. 나의 첫 번째 시도는 Dijikstra의 알고리즘을 사용하게 했으며 다음은 코딩에 대한 나의 시도를 보여줍니다.
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Vertex implements Comparable<Vertex>
{
public final String name;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) { name = argName; }
public String toString() { return name; }
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}
class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String[] args)
{
// mark all the vertices
Vertex A = new Vertex("0");
Vertex B = new Vertex("1");
Vertex C = new Vertex("2");
Vertex D = new Vertex("3");
Vertex E = new Vertex("4");
Vertex F = new Vertex("5");
Vertex G = new Vertex("6");
Vertex H = new Vertex("7");
Vertex I = new Vertex("8");
Vertex J = new Vertex("9");
Vertex K = new Vertex("10");
Vertex L = new Vertex("11");
// set the edges and weight
A.adjacencies = new Edge[]{ new Edge(D, 1) };
A.adjacencies = new Edge[]{ new Edge(F, 1) };
B.adjacencies = new Edge[]{ new Edge(E, 1) };
// C.adjacencies = new Edge[]{ new Edge(D, 1) };
// D.adjacencies = new Edge[]{ new Edge(A, 1) };
D.adjacencies = new Edge[]{ new Edge(C, 1) };
D.adjacencies = new Edge[]{ new Edge(L, 1) };
E.adjacencies = new Edge[]{ new Edge(B, 1) };
// E.adjacencies = new Edge[]{ new Edge(F, 1) };
// F.adjacencies = new Edge[]{ new Edge(A, 1) };
F.adjacencies = new Edge[]{ new Edge(E, 1) };
F.adjacencies = new Edge[]{ new Edge(H, 1) };
// G.adjacencies = new Edge[]{ new Edge(H, 1) };
// H.adjacencies = new Edge[]{ new Edge(F, 1) };
H.adjacencies = new Edge[]{ new Edge(G, 1) };
H.adjacencies = new Edge[]{ new Edge(I, 1) };
// I.adjacencies = new Edge[]{ new Edge(H, 1) };
I.adjacencies = new Edge[]{ new Edge(J, 1) };
// J.adjacencies = new Edge[]{ new Edge(I, 1) };
J.adjacencies = new Edge[]{ new Edge(K, 1) };
// K.adjacencies = new Edge[]{ new Edge(J, 1) };
// L.adjacencies = new Edge[]{ new Edge(D, 1) };
computePaths(A); // run Dijkstra
System.out.println("Distance to " + B + ": " + B.minDistance);
List<Vertex> path = getShortestPathTo(B);
System.out.println("Path: " + path);
}
}
다시 말하지만, 목표는 0에서 1로 가는 것입니다. 가장 빠른 경로는 노드 0 > 5 > 4 > 1 또는 (A > F > E > B) 하지만 이 시스템이 작동하도록 하는 방법을 알 수 없습니다. 이와 관련하여 도움을 주시면 감사하겠습니다!
안부,
도움이 필요한 일상의 괴짜!
추신: 이것은 오류 코드입니다. 수신:
Exception in thread "main" java.lang.NullPointerException
at Dijkstra.computePaths(name.java:42)
at Dijkstra.main(name.java:111)
참조 솔루션
방법 1:
There are some standard methods.
Method A: You record all points that you could possibly reach and their distance. You start with the start point at a distance 0. For each point you find which neighbours it has, in order of distance from nearest to farthest.
You then add a new point: The point that you add is a point that you haven't added yet with the closest distance to the starting point. You would go from any reachable point to its nearest neighbour that isn't in your list yet. And out of all the possibilities you take the point that is closest to your starting point (for an efficient calculation you use priority list. If you went from X to Y, adding Y, you change X in the priority list so you go the next‑nearest neighbour that it has, or remove it completely if all its neighbours have been added. And you add Y with its nearest neighbour that hasn't been added yet).
The calculation ends when you added the end point.
If you look at a street map, this algorithm has the problem that it doesn't actually try to get to the goal. If start and end point are 100 miles apart, it will try all points in a 100 mile radius around the start, roughly. If the distance data is suitable, you replace every distance (X, Y) with the distance (X, Y), minus the amount that you get closer to your goal by going from X to Y. The search will be much quicker because now it prefers points along the line from start to end. If the triangular equation holds, and there is a direct line from start to end, the algorithm will now immediately pick that direct line.
(by Usman Khan、gnasher729)