Re: [新聞] 超狂數學教授活用演算法 高鐵分段買票竟較便宜消失
推
08/15 14:34,
08/15 14:34
這個證法很簡單
假設p到q有最短路徑p,v1,v2.....,vn,q. 那是必p到vk(vk屬於v1,v2...vn)最短路徑
為p,v1,v2...vk
上述話的證明很簡單，用簡單的反證法即可得證
（假設p到vk有最短路徑叫p,w1...vk,而不是p,v1...vk 那p到q就會有最短路徑p,w1...v
k...q,與原命題不合，矛盾）
依據上述，所以只要徵求p到任何連接p的點取最短路徑的話，就可以取得p到任何一
點的最短路徑（當然包含原問題的終點q)
這證法是不是很簡單呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.172.83.208
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1502788591.A.D7B.html
→
08/15 17:17, , 1F
08/15 17:17, 1F
推
08/15 17:18, , 2F
08/15 17:18, 2F
我不是教授，只是這個證明應該任何圖論或演算法的教授會講
最近一次聽到的應該是成大研究所圖論課教授講的
→
08/15 17:19, , 3F
08/15 17:19, 3F
推
08/15 17:20, , 4F
08/15 17:20, 4F
※ 編輯: jpopaholic (1.172.83.208), 08/15/2017 17:27:24
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 10 之 12 篇)：