我發現Dijkstra的算法并將其實現到我創建的圖表中 - 它顯示了我當地的地圖代碼工作正常，但我希望它顯示它訪問過的所有節點，以便從源節點到達位置Node。例如：如果我將源節點設置為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++){
2 回答
郎朗坤
TA貢獻1921條經驗 獲得超9個贊
最簡單的方法是跟蹤每個節點的前身。到達結束節點后，您可以回溯以找出您來自哪里。
添加初始化
int [] comeFrom = new int[vertices];
改變
if(newKey<distance[vertexV])
distance[vertexV] = newKey;
自
if(newKey<distance[vertexV]) {
distance[vertexV] = newKey;
comeFrom[vertexV] = vertexU;
}
以及打印輸出時
List<Integer> path = new ArrayList();
int pos = LocationOfChosenUser;
while(pos != sourceVertex) {
path.add(pos);
pos = comeFrom[pos];
}
for (int i=path.size()-1; i>=0; i--) {
System.out.print(path.get(i));
if (i > 0) System.out.print(" -> ");
}
翻閱古今
TA貢獻1780條經驗 獲得超5個贊
每次更新距離數組時，都需要跟蹤到達節點的路徑。這可以通過多種方式完成，我建議使用一個數組來存儲為在距離數組中實現距離而采取的步驟。
distance[vertexV] = newKey;
lastStep[vertexV] = vertexU;
算法完成后，可以將路徑從目標遍歷回起點?；旧?，你這樣做：
int location = LocationOfChosenUser;
System.out.print(LocationOfChosenUser);
while (location != sourceVertex) {
location = lastStep[LocationOfChosenUser];
System.out.print(" <- " + location);
}
System.out.println();
此順序為您提供相反的順序（因此為箭頭）。您將如何存儲數字并將其反轉留給您進行練習。<-
添加回答
舉報
0/150
提交
取消