迪杰斯特拉算法总结.docx

总结最短路径算法关键先把已知最短路径顶点集(只有一个源点) 和未知的顶点分开然后依次把未知集合的顶点按照最短路径(这里 特别强调一下是源点到该顶点的路径权重和不仅仅是指它和父结 点之间的权重一开始就是在没有这个问题弄清楚)加入到已知结点 集中在加入时可以记录每个顶点的最短路径也可以在加入完毕 后回溯找到每个顶点的最短路径和权重 迪杰斯特拉算法用于求解一个有向图也 可以是无向图无向图是有向图的一种