12 thoughts on “

  1. 最短路徑的權重(長度)可以是正的、負的、零。

    兩點之間不相通,沒有最短路徑的時候,我們習慣將權重值設定為無限大(理論上)。如此一來就滿足了relaxation的不等式。

    又或者設定為一個足夠大、而且經過運算之後不會溢位的數(實作時)。比方說,想要做relaxtion判斷,必須確保d[i] + w[i][j]不會溢位。

    但是我們不會設為零。零的意義是:兩點之間相通,存在最短路徑,而且權重是零。

    同樣的道理,adjacency matrix兩點沒有連結,我們習慣將權重值設定為無限大(理論上),而不是零。

    因此這段程式碼是沒有錯誤的。應該說這段程式碼省略了adjacency matrix w[][]初始化的部分,導致了誤會。

    為了避免誤會,我當初想到了兩種解法:一、補足程式碼,二、另外做說明。

    解法一,本站所有程式碼都沒有針對adjacency matrix初始化,統一風格、避免冗長、方便閱讀。我沒有採用解法一。

    解法二,在先前的段落「兩點之間沒有邊(兩點不相鄰)」,我有提到這件事。我採用了解法二。

    不過很不幸的,現在看來這個解法似乎不是對每個人都有效。至於要如何改善呢?我也不知道。我至今沒有想到什麼簡單俐落的方法。

  2. Hi,
    先感謝你分享演算法,我參考了一些你的文章,寫程式驗證.
    我想反應Single Source Shortest Paths:
    Label Setting Algorithm + Priority Queue
    中的程式碼,
    因為adjacency matrix 兩點沒連結的值是零
    如果加入Priority Queue時不多判斷這點
    d[a] + w[a][b] 排序的結果就會是錯誤的.

    http://www.csie.ntnu.edu.tw/~u91029/Path.html
    //code
    // 比大小的工作,交由Priority Queue處理。
    for (int b=0; b<9; b++)
    if (!visit[b]) //須改為if (!visit[b] &&w[a][b]!=0 )
    PQ.push( (Edge){a, b, d[a] + w[a][b]} );
    // end of code

  3. // yours
    logN   N       N 
      ∑   --- log ---
     i=1  2^i     2^i
    
    // correct
    logN       N       N 
      ∑   2^i --- log ---
     i=1      2^i     2^i
    
    = N log(N) + N log(N/2) + N log(N/4) + ... + N log(1)
    
    = O(NlogN)
    

    謝謝,煮完飯再來改。

  4. 請教版主,http://www.csie.ntnu.edu.tw/~u91029/Point2.html 的Closest Pair一欄中你提到最後一種方法是 O(N logN logN)的,但我認為應該是O(N logN)的。。原因在於某處,你可以檢索“依照Y座標排序。O(NlogN)”快速找到該處,這裡的N並沒有原來的N那麼大。。實際計算應該為O( ∑{i=1->logN} (N/(2^i)) log(N/(2^i)) ),可以證明這是O(N logN)的。
    最後祝願貴站越辦越好!

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s