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();
此順序為您提供相反的順序(因此為箭頭)。您將如何存儲數字并將其反轉留給您進行練習。<-
添加回答
舉報