1.问题描述
单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点s属于V，求从s到其余各结点的最短路径，其中，s称为源点，边上的权值为非负。
求下图中以结点0为源点的单源最短路径。
示意图.png
2.迪杰斯特拉算法
首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。
3.过程
设d[]为路径权值长度；path[]为上级源点编号（我们规定对于目前无法到达的结点，路径长度为无穷大，从自己到自己本身的结点的path[]=-1）
流程图.png
4.算法复杂性
对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。
5.贪心分析
（1）最优子结构性质
求从结点0出发求出到所有结点的最短路径——原问题
当我们通过贪心策略（选择最短路径【迪杰斯特拉算法】）将结点2加入到源点序列之后；
求从（0，2）结点序列到达其他所有结点的最短路径——子问题
可以看出原问题与子问题明显具有最优子结构性质。
（2）最优量度标准
对于该问题，这里我们采取【迪杰斯特拉算法】作为最优量度标准。
