我找到并实现了Dijkstra算法到我创建的图中 - 它展示了我当地地区的地图。代码运行良好,但我希望它显示所有访问过的节点,以便从源节点到达位置节点。例如:如果我将源节点设置为1(Banstead),将位置节点设置为4(Whteleafe)- 我希望它将访问的节点存储在一个数组中,如Array = {1,2,4}。有什么想法吗?我想将其放在FXML文件中,并将节点作为椭圆形,并用线连接它们 - 但为了这样做,我需要存储访问过的节点的值。
package dijkstras;
public class Dijkstras {
static class createGraph{
int vertices;
int matrix[][];
public createGraph(int vertex){
this.vertices = vertex;
matrix = new int[vertex][vertex];
}
public void edge(int source, int destination, int weight){
matrix[source][destination] = weight;
matrix[destination][source] = weight;
}
int getMinVertex(boolean [] mst, int [] key){
int minKey = Integer.MAX_VALUE;
int vertex = -1;
for (int i = 1; i < vertices; i++) {
if(mst[i]==false && minKey>key[i]){
minKey = key[i];
vertex =i;
}
}
return vertex;
}
public void dijkstras(int sourceVertex){
boolean[] spt = new boolean[vertices];
int [] distance = new int[vertices];
int infinity = Integer.MAX_VALUE;
//setting all distances to infinity
for(int i=1; i<vertices; i++){
distance[i] = infinity;
}
//test for starting vertext = 1
distance[sourceVertex] = 1;
//create tree
for(int i=1; i<vertices; i++){
int vertexU = getMinVertex(spt, distance);
spt[vertexU] = true;
//go through all possible paths adjacent to vertex
for(int vertexV=1; vertexV<vertices; vertexV++){
//check if edge between Vu and Vv exists
if(matrix[vertexU][vertexV]>0){
//checks vertexV exists and if distance is not infinite
if(spt[vertexV]==false && matrix[vertexU][vertexV]!=infinity){
int newKey = matrix[vertexU][vertexV] + distance[vertexU];
if(newKey<distance[vertexV])
distance[vertexV] = newKey;
}
}
}
}
System.out.println();
printDijkstras(sourceVertex, distance);
}
public void printDijkstras(int sourceVertex, int [] key){
System.out.println("Dijkstra Algorithm:");
int LocationOfChosenUser = 10;
System.out.println("Source Vertex: "+ sourceVertex + " to " +
LocationOfChosenUser + " distance: " + (key[LocationOfChosenUser]-1));
}
}
public static void graph() {
int vertices = 18;
createGraph graph = new createGraph(vertices);
int sourceVertex = 8;
//adding all nodes
graph.edge(1,2,4); graph.edge(1,17,3);
graph.edge(2,1,4); graph.edge(2,4,4); graph.edge(2,10,5);
graph.edge(3,4,1); graph.edge(3,6,5); graph.edge(3,5,2);
graph.edge(4,2,4); graph.edge(4,3,1); graph.edge(4,5,2);
graph.edge(5,4,2); graph.edge(5,3,2); graph.edge(5,6,3); graph.edge(5,9,4); graph.edge(5,10,5);
graph.edge(6,3,5); graph.edge(6,5,3); graph.edge(6,7,2); graph.edge(6,9,2);
graph.edge(7,6,2); graph.edge(7,8,5);
graph.edge(8,7,5); graph.edge(8,9,4); graph.edge(8,12,5);
graph.edge(9,5,4); graph.edge(9,8,4); graph.edge(9,11,5); graph.edge(9,6,2);
graph.edge(10,2,5); graph.edge(10,5,5); graph.edge(10,13,1);graph.edge(10,14,3); graph.edge(10,17,6);
graph.edge(11,9,5); graph.edge(11,12,3); graph.edge(11,13,3);
graph.edge(12,8,5); graph.edge(12,11,3); graph.edge(12,15,4);
graph.edge(13,11,3); graph.edge(13,10,1); graph.edge(13,14,2);
graph.edge(14,10,3); graph.edge(14,13,2); graph.edge(14,16,6); graph.edge(14,15,6);
graph.edge(15,12,4); graph.edge(15,14,5); graph.edge(15,16,9);
graph.edge(16,15,9); graph.edge(16,17,1); graph.edge(16,14,6);
graph.edge(17,1,3); graph.edge(17,16,1);
graph.dijkstras(sourceVertex);
}
public static void main(String[] args){
graph();
}
}
正如您所看到的,我将sourceVertex设置为8,将LocationVertex(所选用户的位置)设置为10。输出结果大致如下:
Dijkstra Algorithm:
Source Vertex: 8 to 10 distance: 12