在R中使用BFS計算最短路徑

我正在與R一起對網絡進行廣度優先搜索。這裏是我到目前爲止的代碼：在R中使用BFS計算最短路徑

shortestPath <- function(v1,v2) { 
    q <- rep(0, 3931) 
    head <- 1 
    head2 <- 0 
    tail <- 1 
    v1$distance <- 0 
    q[tail] <- v1 
    while(head <= tail) { 
    v <- q[head] 
    head <- head + 1 
    if(v==v2) { 
     return(v$distance) 
     } 
    vEdges <- get.neighborhood(net, v) 
    m <- rep(0,3931) 
    m[head2] <- v 
    head2 <- head2 + 1 
    for(n in vEdges) { 
    if(!(n %in% m)) { 
     n$distance <- v$distance + 1 
     m[head2] <- n 
     head2 <- head2 + 1 
     tail <- tail + 1 
     q[tail] <- n 
     } 
    } 
    } 
}

我不太清楚發生了什麼事情。它只是無限地陷入while循環。我正在處理工作的網絡是完全連接的。我認爲這只是一個小問題，我沒有看到，如果有人能夠讓我朝着解決這個問題的正確方向發展，那會很棒。我可能不像典型的R用戶那麼有經驗。

謝謝。

來源

2013-04-02 user1547050

縮進代碼可以更容易地查看哪些代碼塊形成單元，請參閱我的編輯以瞭解如何縮進代碼。 –

你可能想看看igraph：http://igraph.sourceforge.net/doc/R/graph.bfs.html。當談到任何類型的算法方法時，幾乎從來沒有必要重新發明R中的方法。 – tcash21

我認爲while循環只是無限循環，因爲head <= tail永遠是TRUE，在圖的末尾head == tail我想？我懷疑head < tail是你的意思？此外，我不相信return從while循環中斷，使用break。

來源

2013-04-02 05:19:42

感謝編輯和您的答案。如果確實爲'head user1547050

在R中使用BFS計算最短路徑

回答

相關問題