圖的問題琴锭，核心是解決3種情況
1.有若干小鎮(zhèn)，小鎮(zhèn)之間有的有路降瞳，有的沒路。現(xiàn)在我想修路蚓胸，使小鎮(zhèn)之間互相連通(A和B之間可能沒有路挣饥，但A通過C可以到B)，請問我現(xiàn)在至少要修幾條路沛膳？
解決方案:
首先要有一個概念扔枫，當一群小鎮(zhèn)互相連通時，我們說锹安，這是一個“連通塊”短荐。嘗試遍歷所有小鎮(zhèn)，由于連通快個數(shù)一定大于1叹哭，那么有n個連通快忍宋，就說明遍歷中斷n-1次，就修n-1條路风罩。
2.我要和可愛迷人善良溫柔的女朋友要從杭州去南京旅游糠排。女朋友說“我們走最短的路徑到南京吧”。但地圖上只標注了城市的兩兩距離(A到B超升，B到C入宦，C到A的形式)哺徊。請問怎么求杭州到南京的最短路徑呢？
解決方案：
中介點概念:假設已知A到B的距離為d1∏颍現(xiàn)在發(fā)現(xiàn)A到C落追，C到B的距離為d2，而且d2<d1涯肩。那么目前C就是中介點轿钠，A到C，C到B的距離之和就是目前A到B的最短距離宽菜。假設A到C的距離為d3,然后我們又發(fā)現(xiàn)谣膳，A到D,D到C的距離d4<d3，那么D就成為A到C的中介點铅乡，經(jīng)過C,D的路線距離就是目前A到B的最短距離继谚。你應該想到了，所謂的中介點其實就是前驅(qū)點阵幸，當前驅(qū)點越來越多花履，直至與A重合時，A到B的最短路徑(包括距離挚赊，途經(jīng)的點)就形成了诡壁。記錄下前驅(qū)點，我們的路線也就確定了荠割。
很容易想到一個問題妹卿，一個點的前驅(qū)點是固定的嗎？回答是no.一個點的前驅(qū)點有可能發(fā)生變化蔑鹦，但一定是以下這種情況:
那么有沒有可能發(fā)生前驅(qū)點被“替換”的情況呢夺克？即:
這種情況是不可能的，因為:
具體算法(Dijsktra)
