单源最短路径问题
给定一个赋权图 G = (V, E)和一个特定顶点s作为输入，找到s到G中每一个其他顶点的最短赋权路径。
无权最短路径（解法可被用来做广度优先遍历）
一个无权图G。使用某个顶点s作为输入参数，要找出从s到所有其他顶点的最短路径。
这里给出一个O( | E | + | V | ）的解法。O( | V | ^2）的解法不做讨论。
对于每个顶点，跟踪三条信息，顶点是否被处理（未处理为F,处理过为T，初始为F），s到此顶点的路径长dv（s初始为0，其他为INFINITY），此顶点之前顶点。
在任意时刻，只存在两种类型的dv不是INFINITY的Unknown顶点，一些顶点的dv=currDist，另一些dv=currDist+1。 一种抽象是保留两个盒子，1号盒子装有dv = currDist的那些未知顶点，而2号盒子装有dv = currDist +1的那些顶点。找出一个合适顶点的测试可以用查找1号盒内的任意顶点v代替。在更新v的临界顶点w后，将w放入2号盒中。
可以使用一个队列进一步简化上述模型。迭代开始时，队列只含有距离为currDist的顶点。当添加距离为currDist+1的那些邻接顶点时，由于它们自队尾入队，因此保证它们直到所有距离为currDist的顶点都被处理之后才处理。
//无权最短路径问题的伪代码下图演示算法运行（该图还包括是否known的变化，代码中是不需要的）
void unweighted( Vertex s ){
//一个队列
Queue<Vertex> q = new Queue<Vertex>( );
//每个顶点初始距离为INFINITY
for each Vertex v
v.dist = INFINITY;
//s初始距离为0
s.dist = 0;
q.enqueue( s );
while( !q.isEmpty( ) ){
Vertex v = q.dequeue( );
//遍历v的邻接顶点
for each Vertex w adjacent to v
//如果dist是INFINITY说明没有处理过
if( w.dist == INFINITY ){
w.dist = v.dist + 1;
w.path = v;
q.enqueue( w );
}
}
}
以v3为开始顶点
