Java 中的 Dijkstra 算法和源更改
Dijkstra Algorithm and Source Change in Java
因此，我正在尝试实施 Dijkstra 算法以找到两个城市之间的最短路径。
到目前为止，我的 类 是：
Edge.java
package com.company;
public class Edge {
private int weight;
private Vertex startVertex;
private Vertex targetVertex;
public Edge(int weight, Vertex startVertex, Vertex targetVertex) {
this.weight = weight;
this.startVertex = startVertex;
this.targetVertex = targetVertex;
}
public double getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public Vertex getStartVertex() {
return startVertex;
}
public void setStartVertex(Vertex startVertex) {
this.startVertex = startVertex;
}
public Vertex getTargetVertex() {
return targetVertex;
}
public void setTargetVertex(Vertex targetVertex) {
this.targetVertex = targetVertex;
}
}
然后 Vertex.java
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Vertex implements Comparable<Vertex> {
private String name;
private List<Edge> adjacenciesList;
private boolean visited;
private Vertex predecessor;
private double distance = Double.MAX_VALUE;
public Vertex(String name) {
this.name = name;
this.adjacenciesList = new ArrayList<>();
}
public void addNeighbour(Edge edge) {
this.adjacenciesList.add(edge);
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Edge> getAdjacenciesList() {
return adjacenciesList;
}
public void setAdjacenciesList(List<Edge> adjacenciesList) {
this.adjacenciesList = adjacenciesList;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Vertex getPredecessor() {
return predecessor;
}
public void setPredecessor(Vertex predecessor) {
this.predecessor = predecessor;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
@Override
public String toString() {
return this.name;
}
@Override
public int compareTo(Vertex otherVertex) {
return Double.compare(this.distance, otherVertex.getDistance());
}
}
和DijkstraShortestPath.java
package com.company;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class DjikstraShortestPath {
public void computeShortestPaths(Vertex sourceVertex){
sourceVertex.setDistance(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(sourceVertex);
sourceVertex.setVisited(true);
while( !priorityQueue.isEmpty() ){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
for(Edge edge : actualVertex.getAdjacenciesList()){
Vertex v = edge.getTargetVertex();
if(!v.isVisited())
{
double newDistance = actualVertex.getDistance() + edge.getWeight();
if( newDistance < v.getDistance() ){
priorityQueue.remove(v);
v.setDistance(newDistance);
v.setPredecessor(actualVertex);
priorityQueue.add(v);
}
}
}
actualVertex.setVisited(true);
}
}
public List<Vertex> getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
现在，在 Main 中，我正在尝试这样的事情：
public static void main(String[] args) throws IOException {
{
int i, j;
DjikstraShortestPath shortestPath = new DjikstraShortestPath();
shortestPath.computeShortestPaths(vertex[0]); // setting the source to vertex[0]
for(i=0; i<cities.size(); i++)
{
System.out.println("from"+vertex[0]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
}
shortestPath.computeShortestPaths(vertex[1]); //changing the source
for(i=0; i<cities.size(); i++)
{
System.out.println("from"+vertex[1]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
}
}
我面临的问题是设置时的初始源（初始城市）顶点[0]产生正确的结果：
例如：
from A to A the distance is 0.0 //A is the main source in this case vertex[0]
path: A
from A to F the distance is 13.5
path: A D C B F
现在，当我将源切换到顶点时[1]
from B to A the distance is 0.0 //wrong because it uses the data from the previous (vertex[0])
path: A //this is wrong too
from B to F the distance is 13.5
path: A D C B F //uses the previous info from vertex[0] even though the source is changed to vertex[1]
尝试将 DijkstraShortestPath.java 中的函数 getShortestPathTo 函数更改为此
public void getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
for(int i = 0; i<path.size(); i++)
{
System.out.println(path.get(i).getName());
}
path.clear();
}
}
使所有顶点都未被访问，现在我面临 "Out of Memory" 问题。堆内存问题，我真的什么都试过了。
如有任何帮助，我们将不胜感激。
大家注意安全，待在家里！
在 computeShortestPaths 的第一次调用期间，您在所有已访问的顶点中写入它们已被访问，以及它们到源的距离。
您在调用 computeShortestPaths 之前不会重置此信息，因此顶点会保留它们的距离和已访问状态（if(!v.isVisited()) 确保您不会为已访问的节点更新任何内容第一次通话）。
因此您需要清除两次调用之间 Vertex 对象中的所有信息，或者（更好地）重构您的代码，以便此信息存储在 DjikstraShortestPath 对象而不是顶点中，然后重置每次你打电话 computeShortestPaths.
您需要在算法开始时将所有距离初始化为无穷大。每个顶点中保存的 distance 是一个 "shortest distance seen so far"，因此如果您将 A 与算法的第一个 运行 的距离保持为 0，则第二个 运行 将假设有一条到 A 的较短路径，它的长度为 0。类似地 visited.
另请参阅 algorithm description on Wikipedia 的第 1 步和第 2 步：
- Mark all nodes unvisited. [...]
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. [...]
它第一次工作是因为 distance 被初始化为 Double.MAX_VALUE 而 visited 被初始化为 false。因此，在再次 运行 算法之前，您需要重置这些：
for(i=0; i<vertex.size; i++)
{
vertex[i].setDistance(Double.MAX_VALUE);
vertex[i].setVisited(false);
}
我也遇到过同样的问题（如果我与你的关系正确的话）-一切都很好，直到我们的原点顶点是我们可以到达有向图中所有其他顶点的顶点。当我们选择一个原始顶点时，问题就开始了，我们无法到达同一有向图中的所有其他顶点。前-
2 4 1
A---->B--------->C----->D
| \ | \ |
7 | 13| 3\ |6
| \ | \ |
v v v vv
E---->F--------->G----->H
1 8 13
以上，如果我们选择可以到达所有其他顶点的顶点 A，即 B、C、D、E、F G 和 H - 我们的代码大部分工作正常。但是，如果我们选择顶点 C，我们只能到达上面的 D、G 和 H。当我们从我们的优先级队列中提取其他无法到达的顶点 B、C、E 和 F 的项目作为最小项目以将它们放入最终最短路径 set/list 时，问题就会开始。这些项目在最短路径 set/list 中将具有不切实际的距离，因为它们无法从 C 到达。此外，当我们跟踪原点 C 的最短路径 set/list 到其他顶点以打印最短路径时，那么我们将得到错误的信息，因为无法到达的顶点也是我们最终最短路径的一部分 set/list.
因此解决方案是限制从我们的优先级队列中提取的最终 set/list 项目的条目，如果该项目具有不切实际的距离。我已经通过下面的代码说明了 -
检查下面注释行下的代码，它限制了任何无法到达的顶点，就好像距离对于我们的最终路径列表是不现实的一样。
//限制路径距离不切实际的Item进入
package com.company.graph;
import java.util.*;
public class ShortestPath_Dijkstra {
public static void main(String...args){
String directedGraph =
"\n\n 2 4 1\n" +
" A---->B--------->C----->D\n" +
" | \ | \ |\n" +
" 7 | \9 13| 3\ |6\n" +
" | \ | \ |\n" +
" v v v vv\n" +
" E---->F--------->G----->H\n" +
" 1 8 13" ;
// We store number instated of letters since in real world every vertex may have full qualified name ex - "LasVegas" instead of just "A"
Map<Integer,String> vertices = new HashMap<>();
vertices.put(0,"A");
vertices.put(1,"B");
vertices.put(2,"C");
vertices.put(3,"D");
vertices.put(4,"E");
vertices.put(5,"F");
vertices.put(6,"G");
vertices.put(7,"H");
Map<Edge, Integer> edges = new HashMap<>();
//Implemented edges as a Map where for each entry - key is a vertex and value is List containing edges i.e. all connecting vertices along with the weight !!
Map<Integer, List<Edge>> verticesEdges = new HashMap<>();
verticesEdges.put(0, new LinkedList<>(List.of(new Edge(1,2), new Edge(4,7),new Edge(5,9) )));
verticesEdges.put(1, new LinkedList<>(List.of(new Edge(2,4))));
verticesEdges.put(2, new LinkedList<>(List.of(new Edge(3,1),new Edge(6,13), new Edge(7,3))));
verticesEdges.put(3, new LinkedList<>(List.of(new Edge(7,6))));
verticesEdges.put(4, new LinkedList<>(List.of(new Edge(5,1) )));
verticesEdges.put(5, new LinkedList<>(List.of(new Edge(6,8) )));
verticesEdges.put(6, new LinkedList<>(List.of(new Edge(7,13))));
verticesEdges.put(7, new LinkedList<>());
Integer origin = 2; // alias C
Map<Integer, Item> pathMap = getShortestPathMap(origin, vertices, verticesEdges);
displayShortestPaths(directedGraph, origin, pathMap, vertices);
}
//Dijkstra function
static Map<Integer, Item> getShortestPathMap(Integer origin, Map<Integer,String> vertices, Map<Integer, List<Edge>> verticesEdges){
Map<Integer, Item> pathMap = new HashMap<>();
PriorityQueue<Item> queue = new PriorityQueue<>();
//Initialization of queue.
vertices.keySet().forEach(v -> {
if(v.equals(origin)){
queue.add(new Item(v, 0, null));
}else {
queue.add(new Item(v));
}
});
while(!queue.isEmpty()){
Item currItem = queue.poll();
//Restrict entry of Items having unrealistic path distances
if(currItem.getDistance() != Integer.MAX_VALUE && currItem.getDistance() >= 0){
pathMap.put(currItem.vertex, currItem);
}
verticesEdges.get(currItem.getVertex()).forEach(edge -> {
//Get item in queue corresponding to vertex of this edge
Item connItem = new Item(edge.getV());
Iterator<Item> iterator = queue.iterator();
boolean found = false;
while(iterator.hasNext()){
Item inQueue = iterator.next();
if(inQueue.equals(connItem)){
connItem = inQueue;
found = true;
break;
}
}
//Update this connection Item distance if more than sum distance of current vertex and connecting edge weight. And also parent as current vertex.
if(found && connItem.getDistance() > currItem.getDistance() + edge.getW()){
queue.remove(connItem);
queue.add(new Item(connItem.getVertex(), currItem.getDistance() + edge.getW(), currItem.getVertex()));
}
});
}
return pathMap;
}
//Display function
static void displayShortestPaths(String directedGraph, Integer origin, Map<Integer, Item> pathMap, Map<Integer,String> vertices){
System.out.println("For a directed Graph - " + directedGraph );
System.out.format("%nShortest Paths to all vertices starting from %S - %n", vertices.get(origin));
vertices.keySet().forEach(v ->{
if(pathMap.get(v)!=null){
System.out.format("%n Shortest path(distance) from %S --> %S is %S", vertices.get(origin), vertices.get(v), pathMap.get(v).getDistance());
System.out.format(" via vertices : ");
Stack<String> path = new Stack<>();
path.push(vertices.get(v));
while(pathMap.get(v).getParent() != null){
v = pathMap.get(v).getParent();
path.push(vertices.get(v));
}
System.out.format("%S", path.pop());
while (!path.empty()){
System.out.format("-->%S", path.pop());
}
}
});
}
// Below class are Data Structures to store and process graph
static class Edge {
Integer v; //Connecting Vertex
Integer w; //weight Of edge
Edge(int v, int w) {
this.v = v;
this.w = w;
}
int getV() { return v; }
int getW() { return w; }
}
static class Item implements Comparable<Item>{
Integer vertex;
Integer distance = Integer.MAX_VALUE;
Integer parent = null;
Item(Integer vertex) {
this.vertex = vertex;
}
Item(Integer vertex, Integer distance, Integer parent) {
this.vertex = vertex;
this.distance = distance;
this.parent = parent;
}
Integer getVertex() { return vertex; }
Integer getDistance() { return distance; }
Integer getParent() { return parent; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Item item = (Item) o;
return vertex.equals(item.vertex);
}
@Override
public int hashCode() {
return Objects.hash(vertex);
}
@Override
public int compareTo(Item item) {
return this.distance - item.distance;
}
}
}
让我们 运行 上面的代码，我想只看到从 C 到可达顶点的最短距离，而不是任何不现实（无法到达）的顶点 -
For a directed Graph -
2 4 1
A---->B--------->C----->D
| \ | \ |
7 | 13| 3\ |6
| \ | \ |
v v v vv
E---->F--------->G----->H
1 8 13
Shortest Paths to all vertices starting from C -
Shortest path(distance) from C --> C is 0 via vertices : C
Shortest path(distance) from C --> D is 1 via vertices : C-->D
Shortest path(distance) from C --> G is 13 via vertices : C-->G
Shortest path(distance) from C --> H is 3 via vertices : C-->H
Process finished with exit code 0
我们还要检查 "if condition" 限制不切实际的条目不会对顶点 A 作为原点的情况造成任何负面影响（即图中所有其他顶点均可到达）-
为此我们需要做 1 行更改来告诉原点顶点现在是 A,
Integer origin = 0; // alias A
For a directed Graph -
2 4 1
A---->B--------->C----->D
| \ | \ |
7 | 13| 3\ |6
| \ | \ |
v v v vv
E---->F--------->G----->H
1 8 13
Shortest Paths to all vertices starting from A -
Shortest path(distance) from A --> A is 0 via vertices : A
Shortest path(distance) from A --> B is 2 via vertices : A-->B
Shortest path(distance) from A --> C is 6 via vertices : A-->B-->C
Shortest path(distance) from A --> D is 7 via vertices : A-->B-->C-->D
Shortest path(distance) from A --> E is 7 via vertices : A-->E
Shortest path(distance) from A --> F is 8 via vertices : A-->E-->F
Shortest path(distance) from A --> G is 16 via vertices : A-->E-->F-->G
Shortest path(distance) from A --> H is 9 via vertices : A-->B-->C-->H
Process finished with exit code 0
因此，我正在尝试实施 Dijkstra 算法以找到两个城市之间的最短路径。 到目前为止，我的 类 是：
Edge.java
package com.company;
public class Edge {
private int weight;
private Vertex startVertex;
private Vertex targetVertex;
public Edge(int weight, Vertex startVertex, Vertex targetVertex) {
this.weight = weight;
this.startVertex = startVertex;
this.targetVertex = targetVertex;
}
public double getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public Vertex getStartVertex() {
return startVertex;
}
public void setStartVertex(Vertex startVertex) {
this.startVertex = startVertex;
}
public Vertex getTargetVertex() {
return targetVertex;
}
public void setTargetVertex(Vertex targetVertex) {
this.targetVertex = targetVertex;
}
}
然后 Vertex.java
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Vertex implements Comparable<Vertex> {
private String name;
private List<Edge> adjacenciesList;
private boolean visited;
private Vertex predecessor;
private double distance = Double.MAX_VALUE;
public Vertex(String name) {
this.name = name;
this.adjacenciesList = new ArrayList<>();
}
public void addNeighbour(Edge edge) {
this.adjacenciesList.add(edge);
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Edge> getAdjacenciesList() {
return adjacenciesList;
}
public void setAdjacenciesList(List<Edge> adjacenciesList) {
this.adjacenciesList = adjacenciesList;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Vertex getPredecessor() {
return predecessor;
}
public void setPredecessor(Vertex predecessor) {
this.predecessor = predecessor;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
@Override
public String toString() {
return this.name;
}
@Override
public int compareTo(Vertex otherVertex) {
return Double.compare(this.distance, otherVertex.getDistance());
}
}
和DijkstraShortestPath.java
package com.company;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class DjikstraShortestPath {
public void computeShortestPaths(Vertex sourceVertex){
sourceVertex.setDistance(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(sourceVertex);
sourceVertex.setVisited(true);
while( !priorityQueue.isEmpty() ){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
for(Edge edge : actualVertex.getAdjacenciesList()){
Vertex v = edge.getTargetVertex();
if(!v.isVisited())
{
double newDistance = actualVertex.getDistance() + edge.getWeight();
if( newDistance < v.getDistance() ){
priorityQueue.remove(v);
v.setDistance(newDistance);
v.setPredecessor(actualVertex);
priorityQueue.add(v);
}
}
}
actualVertex.setVisited(true);
}
}
public List<Vertex> getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
现在，在 Main 中，我正在尝试这样的事情：
public static void main(String[] args) throws IOException {
{
int i, j;
DjikstraShortestPath shortestPath = new DjikstraShortestPath();
shortestPath.computeShortestPaths(vertex[0]); // setting the source to vertex[0]
for(i=0; i<cities.size(); i++)
{
System.out.println("from"+vertex[0]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
}
shortestPath.computeShortestPaths(vertex[1]); //changing the source
for(i=0; i<cities.size(); i++)
{
System.out.println("from"+vertex[1]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
}
}
我面临的问题是设置时的初始源（初始城市）顶点[0]产生正确的结果：
例如：
from A to A the distance is 0.0 //A is the main source in this case vertex[0]
path: A
from A to F the distance is 13.5
path: A D C B F
现在，当我将源切换到顶点时[1]
from B to A the distance is 0.0 //wrong because it uses the data from the previous (vertex[0])
path: A //this is wrong too
from B to F the distance is 13.5
path: A D C B F //uses the previous info from vertex[0] even though the source is changed to vertex[1]
尝试将 DijkstraShortestPath.java 中的函数 getShortestPathTo 函数更改为此
public void getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
for(int i = 0; i<path.size(); i++)
{
System.out.println(path.get(i).getName());
}
path.clear();
}
}
使所有顶点都未被访问，现在我面临 "Out of Memory" 问题。堆内存问题，我真的什么都试过了。
如有任何帮助，我们将不胜感激。
大家注意安全，待在家里！
在 computeShortestPaths 的第一次调用期间，您在所有已访问的顶点中写入它们已被访问，以及它们到源的距离。
您在调用 computeShortestPaths 之前不会重置此信息，因此顶点会保留它们的距离和已访问状态（if(!v.isVisited()) 确保您不会为已访问的节点更新任何内容第一次通话）。
因此您需要清除两次调用之间 Vertex 对象中的所有信息，或者（更好地）重构您的代码，以便此信息存储在 DjikstraShortestPath 对象而不是顶点中，然后重置每次你打电话 computeShortestPaths.
您需要在算法开始时将所有距离初始化为无穷大。每个顶点中保存的 distance 是一个 "shortest distance seen so far"，因此如果您将 A 与算法的第一个 运行 的距离保持为 0，则第二个 运行 将假设有一条到 A 的较短路径，它的长度为 0。类似地 visited.
另请参阅 algorithm description on Wikipedia 的第 1 步和第 2 步：
- Mark all nodes unvisited. [...]
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. [...]
它第一次工作是因为 distance 被初始化为 Double.MAX_VALUE 而 visited 被初始化为 false。因此，在再次 运行 算法之前，您需要重置这些：
for(i=0; i<vertex.size; i++)
{
vertex[i].setDistance(Double.MAX_VALUE);
vertex[i].setVisited(false);
}
我也遇到过同样的问题（如果我与你的关系正确的话）-一切都很好，直到我们的原点顶点是我们可以到达有向图中所有其他顶点的顶点。当我们选择一个原始顶点时，问题就开始了，我们无法到达同一有向图中的所有其他顶点。前-
2 4 1
A---->B--------->C----->D
| \ | \ |
7 | 13| 3\ |6
| \ | \ |
v v v vv
E---->F--------->G----->H
1 8 13
以上，如果我们选择可以到达所有其他顶点的顶点 A，即 B、C、D、E、F G 和 H - 我们的代码大部分工作正常。但是，如果我们选择顶点 C，我们只能到达上面的 D、G 和 H。当我们从我们的优先级队列中提取其他无法到达的顶点 B、C、E 和 F 的项目作为最小项目以将它们放入最终最短路径 set/list 时，问题就会开始。这些项目在最短路径 set/list 中将具有不切实际的距离，因为它们无法从 C 到达。此外，当我们跟踪原点 C 的最短路径 set/list 到其他顶点以打印最短路径时，那么我们将得到错误的信息，因为无法到达的顶点也是我们最终最短路径的一部分 set/list.
因此解决方案是限制从我们的优先级队列中提取的最终 set/list 项目的条目，如果该项目具有不切实际的距离。我已经通过下面的代码说明了 -
检查下面注释行下的代码，它限制了任何无法到达的顶点，就好像距离对于我们的最终路径列表是不现实的一样。 //限制路径距离不切实际的Item进入
package com.company.graph;
import java.util.*;
public class ShortestPath_Dijkstra {
public static void main(String...args){
String directedGraph =
"\n\n 2 4 1\n" +
" A---->B--------->C----->D\n" +
" | \ | \ |\n" +
" 7 | \9 13| 3\ |6\n" +
" | \ | \ |\n" +
" v v v vv\n" +
" E---->F--------->G----->H\n" +
" 1 8 13" ;
// We store number instated of letters since in real world every vertex may have full qualified name ex - "LasVegas" instead of just "A"
Map<Integer,String> vertices = new HashMap<>();
vertices.put(0,"A");
vertices.put(1,"B");
vertices.put(2,"C");
vertices.put(3,"D");
vertices.put(4,"E");
vertices.put(5,"F");
vertices.put(6,"G");
vertices.put(7,"H");
Map<Edge, Integer> edges = new HashMap<>();
//Implemented edges as a Map where for each entry - key is a vertex and value is List containing edges i.e. all connecting vertices along with the weight !!
Map<Integer, List<Edge>> verticesEdges = new HashMap<>();
verticesEdges.put(0, new LinkedList<>(List.of(new Edge(1,2), new Edge(4,7),new Edge(5,9) )));
verticesEdges.put(1, new LinkedList<>(List.of(new Edge(2,4))));
verticesEdges.put(2, new LinkedList<>(List.of(new Edge(3,1),new Edge(6,13), new Edge(7,3))));
verticesEdges.put(3, new LinkedList<>(List.of(new Edge(7,6))));
verticesEdges.put(4, new LinkedList<>(List.of(new Edge(5,1) )));
verticesEdges.put(5, new LinkedList<>(List.of(new Edge(6,8) )));
verticesEdges.put(6, new LinkedList<>(List.of(new Edge(7,13))));
verticesEdges.put(7, new LinkedList<>());
Integer origin = 2; // alias C
Map<Integer, Item> pathMap = getShortestPathMap(origin, vertices, verticesEdges);
displayShortestPaths(directedGraph, origin, pathMap, vertices);
}
//Dijkstra function
static Map<Integer, Item> getShortestPathMap(Integer origin, Map<Integer,String> vertices, Map<Integer, List<Edge>> verticesEdges){
Map<Integer, Item> pathMap = new HashMap<>();
PriorityQueue<Item> queue = new PriorityQueue<>();
//Initialization of queue.
vertices.keySet().forEach(v -> {
if(v.equals(origin)){
queue.add(new Item(v, 0, null));
}else {
queue.add(new Item(v));
}
});
while(!queue.isEmpty()){
Item currItem = queue.poll();
//Restrict entry of Items having unrealistic path distances
if(currItem.getDistance() != Integer.MAX_VALUE && currItem.getDistance() >= 0){
pathMap.put(currItem.vertex, currItem);
}
verticesEdges.get(currItem.getVertex()).forEach(edge -> {
//Get item in queue corresponding to vertex of this edge
Item connItem = new Item(edge.getV());
Iterator<Item> iterator = queue.iterator();
boolean found = false;
while(iterator.hasNext()){
Item inQueue = iterator.next();
if(inQueue.equals(connItem)){
connItem = inQueue;
found = true;
break;
}
}
//Update this connection Item distance if more than sum distance of current vertex and connecting edge weight. And also parent as current vertex.
if(found && connItem.getDistance() > currItem.getDistance() + edge.getW()){
queue.remove(connItem);
queue.add(new Item(connItem.getVertex(), currItem.getDistance() + edge.getW(), currItem.getVertex()));
}
});
}
return pathMap;
}
//Display function
static void displayShortestPaths(String directedGraph, Integer origin, Map<Integer, Item> pathMap, Map<Integer,String> vertices){
System.out.println("For a directed Graph - " + directedGraph );
System.out.format("%nShortest Paths to all vertices starting from %S - %n", vertices.get(origin));
vertices.keySet().forEach(v ->{
if(pathMap.get(v)!=null){
System.out.format("%n Shortest path(distance) from %S --> %S is %S", vertices.get(origin), vertices.get(v), pathMap.get(v).getDistance());
System.out.format(" via vertices : ");
Stack<String> path = new Stack<>();
path.push(vertices.get(v));
while(pathMap.get(v).getParent() != null){
v = pathMap.get(v).getParent();
path.push(vertices.get(v));
}
System.out.format("%S", path.pop());
while (!path.empty()){
System.out.format("-->%S", path.pop());
}
}
});
}
// Below class are Data Structures to store and process graph
static class Edge {
Integer v; //Connecting Vertex
Integer w; //weight Of edge
Edge(int v, int w) {
this.v = v;
this.w = w;
}
int getV() { return v; }
int getW() { return w; }
}
static class Item implements Comparable<Item>{
Integer vertex;
Integer distance = Integer.MAX_VALUE;
Integer parent = null;
Item(Integer vertex) {
this.vertex = vertex;
}
Item(Integer vertex, Integer distance, Integer parent) {
this.vertex = vertex;
this.distance = distance;
this.parent = parent;
}
Integer getVertex() { return vertex; }
Integer getDistance() { return distance; }
Integer getParent() { return parent; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Item item = (Item) o;
return vertex.equals(item.vertex);
}
@Override
public int hashCode() {
return Objects.hash(vertex);
}
@Override
public int compareTo(Item item) {
return this.distance - item.distance;
}
}
}
让我们 运行 上面的代码，我想只看到从 C 到可达顶点的最短距离，而不是任何不现实（无法到达）的顶点 -
For a directed Graph -
2 4 1
A---->B--------->C----->D
| \ | \ |
7 | 13| 3\ |6
| \ | \ |
v v v vv
E---->F--------->G----->H
1 8 13
Shortest Paths to all vertices starting from C -
Shortest path(distance) from C --> C is 0 via vertices : C
Shortest path(distance) from C --> D is 1 via vertices : C-->D
Shortest path(distance) from C --> G is 13 via vertices : C-->G
Shortest path(distance) from C --> H is 3 via vertices : C-->H
Process finished with exit code 0
我们还要检查 "if condition" 限制不切实际的条目不会对顶点 A 作为原点的情况造成任何负面影响（即图中所有其他顶点均可到达）- 为此我们需要做 1 行更改来告诉原点顶点现在是 A,
Integer origin = 0; // alias A
For a directed Graph -
2 4 1
A---->B--------->C----->D
| \ | \ |
7 | 13| 3\ |6
| \ | \ |
v v v vv
E---->F--------->G----->H
1 8 13
Shortest Paths to all vertices starting from A -
Shortest path(distance) from A --> A is 0 via vertices : A
Shortest path(distance) from A --> B is 2 via vertices : A-->B
Shortest path(distance) from A --> C is 6 via vertices : A-->B-->C
Shortest path(distance) from A --> D is 7 via vertices : A-->B-->C-->D
Shortest path(distance) from A --> E is 7 via vertices : A-->E
Shortest path(distance) from A --> F is 8 via vertices : A-->E-->F
Shortest path(distance) from A --> G is 16 via vertices : A-->E-->F-->G
Shortest path(distance) from A --> H is 9 via vertices : A-->B-->C-->H
Process finished with exit code 0