[查用] All-Pairs Shortest Path 與 Floyd's Algorithm


All-Pairs Shortest Path

目標：任兩點之間的最短距離

這個圖之中edge上面的數字代表距離

這個圖沒有所謂的root跟 leaf


找不到一個點，他的edge只有單一方向


演算法 Floyd's Algorithm
找兩點之間的距離
演算法核心：
找 i 到 j 的距離，與 i 經過 k 再到 j 的距離做比較

取比較小的

例如圖上的 C -> D
直接走的距離是 5
但如果走 C -> E -> D 的距離只有 3 比較短！


留言

張貼留言

這個網誌中的熱門文章

[筆記] CRLF跟LF之區別 --- 隱形的 bug

圖片
最近在當助教時，偶然間遇到一個隱形的Bug 為什麼稱之為隱形呢？ 請見下面兩張圖 說明：answer.txt 與 answer_test.txt 這兩個檔案的內容用文字編輯器打開時，完全一模一樣，但是我在使用 diff 指令的時候居然出現判定為每一行都不一樣的情形 指令 diff answer.txt answer_test.txt 由最上面第一張圖中可以注意到，answer.txt 的檔案大小是 958 byte answer_test.txt 的檔案大小則為 924 byte 此時不禁讓我疑惑到，兩個檔案內容相同，空白數量也完全相同的情況下，造成檔案大小不同的原因是什麼呢？ 下圖說明了一切 原來在 answer.txt 檔案當中，他的換行是採用 CRLF 而 answer_test.txt 的換行則是一般UNIX的情形 LF # 以下感謝梁浩穎同學解釋 CRLF 就是 \r\n 是只有在 windows 系統在用的形式 所有的 UNIX 系統都是用 \n   (的確，上圖中的 answer.txt 是用windows 7系統的記事本所編輯的，answer_test.txt 則是用 mac 系統透過 sublime text 所編輯的) CR是carriage return的意思， 也就是\r  LF是line feed的意思，也就是\n 這就是為什麼有些檔案從unix系統拿去windows上面看 會變成全部都在同一行 因為只有LF 他不知道是換行 windows只吃CRLF 除了一些比較聰明的文字編輯器會 分的出來 不過其實，CRLF才是真正的打字機運作方式，你可以想像：打字機打到最右邊，要先return到最左邊之後，再往下一行， 所以是CRLF 如果想要清空 answer.txt 裡面所有的 \r 的話，可以使用以下指令 tr -d '\r’ answer.txt # 遇到這個隱形的bug真是難得的好玩經驗，分享給大家 :)
Read more »

[ML筆記] Batch Normalization

圖片
Batch Normalization 本篇為台大電機系李宏毅老師 Machine Learning and having it Deep and Structured (2017)  課程筆記 上課影片： https://www.youtube.com/watch?v=BZh1ltr5Rkg 先從 Feature scaling 或是稱作 Feature Normalization 說起 假設 x1 跟 x2 的數值差距很大 x1 值的範圍 1,2,3,4, ... x2 值的範圍 100, 200, 300, … x1 的 weight 是 w1，x2 的 weight 是 w2 w1 前面乘的值比較小，所以他對於結果的影響比較小 w2 前面乘的值比較大，所以他對於結果的影響比較大
Read more »

[筆記] 統計實習(1) SAS 基礎用法 (匯入資料並另存SAS新檔，SUBSTR，計算總和與平均，BMI)

圖片
使用版本 SAS 9.3 繁體中文 OS: windows xp 匯入資料並另存成SAS新檔 step 1: 匯入資料 step 2: 選擇匯入檔案類型 step 3: 去資料夾 Browse 找尋要匯入的資料檔案 (這裡我命名為Man) step 4: 選好檔案後按OK step 5: 然後按Next step 6: 成功匯入excel資料  (我命名為 Man)，欲找尋這個檔案在哪 -> 按左側的資料館 step 7: 再選Work資料夾 step 8: 就會看到剛剛被我命名的 Man 檔案資料 step 9: 做些簡單的資料分析，在Editor視窗中寫code             Data test;             set man;             run;             以上code做的事會把這個 man (大小寫沒差)資料表複製一份，另命名成 test 存起來 step 10: 要複製另存成SAS檔，使用libname語法 後面放 目錄名稱'檔案路徑'               這裡的目錄名稱為 J 路徑為 '   ' 之中。                      step 11: 如此的code寫完，按下小人圖示提交執行程式 step 12: 會發現資料館裡面，多了一個名稱為 J 的資料夾目錄 step 13: 在 J 資料夾目錄裡面會成功看到被複製出來的名稱為 test 的資料 step 14: 實際跑到剛剛在 '   ' 之中的路徑看，也會看到test資料 SAS SUBSTR的用法 substr (sub string)顧名思義就是將一串文字當中切割出來一條子字串 語法為 新Table欄位名稱 = SUBSTR( Table欄位名稱 , 起始bit位置 , 要往後多少位元 ) 常用於將日期年月日分別切割出來變成數字來運算 step 1: 在Editor當中輸入語法 以第一橫排 16/10/1986為例 要取得日期DAY要從time欄位的第1個bit開始往後切長度
Read more »

[ML筆記] Ensemble - Bagging, Boosting & Stacking

圖片
ML Lecture 27: Ensemble 本篇為台大電機系李宏毅老師 Machine Learning (2016) 課程筆記 上課影片： https://www.youtube.com/watch?v=tH9FH1DH5n0 課程網 (投影片出處)： http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML16.html Ensemble 方法其實就是 “團隊合作” 好幾個模型一起上的方法 假如我們手上有一堆 Classifier ，這些 Classifier 每個都有不同的屬性， 要把他們集合起來一起合作，集合再一起需要用比較好的方法 以下來介紹一些 Ensemble 的方法 Bagging
Read more »