今天去面試遇到一個(gè)算法 Dijkstra 算法(迪杰斯特拉算法),解決求最短路徑問(wèn)題
快速理解:
1：選取初始節(jié)點(diǎn)作為一個(gè)集合份乒，D（v）表示初始節(jié)點(diǎn)到V節(jié)點(diǎn)的最短路徑
2：所有能直接到達(dá)V的節(jié)點(diǎn)路徑記為D（v）=距離叛买，不能直接到達(dá)的節(jié)點(diǎn)路徑記為D（v）=無(wú)窮
3：選取D（v）最小的節(jié)點(diǎn)加入初始節(jié)點(diǎn)集合，最短路徑記為D(w)=min（D（w）到忽，D（v）+j（v,w））（j（v,w）為節(jié)點(diǎn)V到W的距離）
4：重復(fù)步驟3，直到所有節(jié)點(diǎn)都加入初始節(jié)點(diǎn)集合
圖理解：
dijkstra圖
