基本概念
源点（Source）路径的开始顶点
终点（Destination）路径的最后一个顶点
单源最短路径问题（SingleSource ShortestPaths Problem）给定一个带权图G=(VE)和图中的一个源点v分别求出从v到图G中其他每个顶点的最短路径长度即路径上权值的总和
单目标最短路径问题（SingleDestination ShortestPaths Problem）找出图中每一顶点v到某指定顶点u的最短路径
单顶点对间最短路径问题（SinglePair ShortestPath Problem）对于某对顶点u和v找出从u到v的一条最短路径
所有顶点对间最短路径问题（AllPairs ShortestPaths Problem）对图中每对顶点u和v找出u到v的最短路径问题
最短路径（Shortest Path）即求两个顶点间长度最短的路径（该长度不是指路径上边数的总和而是指路径上各边权值的总和）
最短距离路径是一个结点序列路径的长度是其权值的和称为距离所以最短路径长度就是最短距离
最短路径（迪杰斯特拉）算法
迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的顺序产生最短路径的方法此方法的基本思想是把图中所有顶点分成两组每一组包括已确定最短路径的顶点第二组包括尚未确定最短路径的顶点按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去直至从vi出发可以到达的所有顶点都包括到第一组中在此过程中总保持从vi到第一组各顶点的最短路径长度都不大于从vi到第二组的任何顶点的最短路径长度另外每一个顶点对应一个距离值第一组的顶点对应的距离值就是从vi到此顶点的只包括第一组的顶点为中间顶点的最短路径长度
具体做法是
() 第一组S只包括源点v第二组T包括其他所有的顶点
() v对应的距离值为第二组的顶点对应的距离值是这样确定的若图中有边＜vvj＞则vj的距离为此边所带的权值否则vj的距离值为一个很大的数（大于所有顶点间的路径长度）然后每次从第二组的顶点中选一个其距离值为最小的vm加入第一组中
() 每往第一组加入一个顶点vm就要对第二组中的各个顶点的距离值进行一次修正修正的原则是若加进vm做中间顶点使从v到vj的最短路径比不加vm的路径为短则要修改vj的距离值
() 如此进行下去直到图中所有顶点都包括在第一组中或再也没有可加入到第一组中的顶点存在为止
