shortest path

我在想single source shortest path的問題。

啞然失笑。回頭想想自己，在做shortest path的時候，都知道找cost最小的路徑。做決定的時候，卻往往選擇cost最高的那條。

Dijkstra演算法中，遇到岔路會先選成本較小的那邊，那是因為根據貪婪法則，以及Dijkstra保證在圖中，不會有負的邊。Bellman-Ford演算法解決了負邊的情況，但仍不能解決有負數迴圈存在的情形。但總的來說，這兩個演算法為的就是，找出到destination的最小cost路徑。

可是我常常反骨。就是知道那是cost高的路線依舊要走。

反骨是好聽的說法，倒不如說愚蠢吧！一條簡單的、到得了終點的路不走，卻跑去走崎嶇顛簸的路。我不知道有沒有沾沾自喜，但我好像因此感到高興？

可能是一種證明個體存在的方法。這樣精神上的滿足將—如果以精神滿足作為path上的cost條件—shortest path的結果導向，以實際情形來看，最不符合經濟效應的路線。

我是個愚蠢的人。不過說起來，用shortest path問題模擬人生的一些選擇，仍有許多問題要考量，並不似在教科書上的習題，把演算法套進去，就會有最佳的解產生。

假如說，在這個graph上，destination永遠到達不了呢？

我把這樣情形的destination表記上無限大∞，那我們依舊找得到shortest path，這個shortest path的代價是無限。代價是無限的路徑，如果在演算法的問題中，我們會選擇嗎？儘管他是一條最短的路徑。

我的問題應該就圍繞在這兩者之上：一是刻意選擇代價高的路徑，二是無限大的destination。這兩者之間好像有些相關。在演算法中，這兩者是不合理的。但在現實生活中，卻被我實行著。

第一點是我一種自我認同的方式，讓我覺得存在。

第二種是我一種信念，兼之在現實生活，weight的值是可以靠努力、找方法去改變他的。

關於shortest path，或許還有更多的問題值得我去探討，不僅是書本上的。