亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

查找兩個節點之間的最短距離

查找兩個節點之間的最短距離

慕村9548890 2022-08-03 10:43:26
我發現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(" -> ");

}


查看完整回答
反對 回復 2022-08-03
?
翻閱古今

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();

此順序為您提供相反的順序(因此為箭頭)。您將如何存儲數字并將其反轉留給您進行練習。<-


查看完整回答
反對 回復 2022-08-03
  • 2 回答
  • 0 關注
  • 160 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號