我们的输入是一个赋权图：与每条边（Vi，Vj)相联系的是穿越该弧的代价（或称为值）Ci,j。一条路径V1V2V3...Vn的值是C1,2 + C2,3 + C3, 4 + .... Cn-1,n，这个值叫做赋权路径长（weighted path length)。而无权路径长（unweighted path length）只是路径上的变数，即N-1。

单源最短路径问题

给定一个赋权图G = （V，E）和一个顶点s作为输入，找出s到G中每一个其他顶点的最短赋权路径。

例如下图：

从v1到v6的最短赋权路径的值是6，它是从v1到v4到v7再到v6的路径。在这两个顶点间的最短无权路径是2。一般来说，当不指明我们讨论的是赋权路径还是无权路径时，如果图是赋权的，那么路径就是赋权的。另外需要注意的是从v6到v1是没有路径的。

又如下图带有负值圈的图：

从v5到v4的路径的值为1,但是通过v5, v4, v2,v5,v4存在一条最短路径，它的值是-5。这条路径仍然不是最短的，因为我们可以在循环中滞留任意长，因此在这两个顶点间的最短路径问题是不确定的。类似，从v1到到v6的最短路径也是不确定的，因为我们可以进入同样的循环，这个循环叫做负值圈（negative-cost cycle）；当它出现时，最短路径问题就是不确定的。有负值的边未必就是坏事，但是它们的出现使问题增加了难度。为方便起见，在没有负值圈时，送s到s的最短路径为0。

无权最短路径

无权有向图

上图是一个无权的图G。使用某个顶点s作为输入参数，我们想要找出从s到所有其他顶点的最短路径。我们只对包含在路径中的边数有兴趣，因此在边上不存在权。显然，这是赋权最短路径问题的特殊情况，因为我们可以为所有的边都赋以权1。

假设我们只对最短路径的长而不是具体的路径本身有兴趣。

设我们选择s是v3.此时我们可以立即说出从s到v3的最短路径是长为0的路径。把这个信息做个标记。

现在我们可以开始找寻所有与s距离为1的定点。这些顶点通过考察与s邻接的那些点可以找到。显然哦我们可以发现，v1和v6与出发s只有一边之遥。标记如下。

现在我们可以开始找出哪些从s出发最短路径为2的顶点，我们找出所有邻接到v1和v6的顶点（距离为1处的顶点），它们的最短路径还不知道。这次搜索告诉我们，到v2和v4的最短路径为2，标记如下

最后通过考察那些与刚被赋值的v2和v4相邻的顶点我们可以发现，v5和v7各有一条三边最短路径。标记如下：

现在所有的顶点都已经被计算。

这种搜索一个图的方法称为广度优先搜索（breadth-first search）。该方法按层处理顶点：距开始点最近的那些顶点首先被赋值，而最远的那些顶点最后被赋值。

用于无权最短路径计算的表的初始配置

对于每个顶点，我们跟踪3个信息。

首先，我们把从s开始到各顶点的距离放到dv一栏中。

开始的时候除s外所有的顶点都是不可达到的，而s的路径长为0。

pv栏中的项为簿记变量，它将使我们能够显示出实际的路径。

Known中的项被处理以后置一。

起初，所有的顶点都不是Known，包括开始顶点。当一个顶点被标记为已知时，我们就确信不会再找到更短的路径，因此对该点的处理已经完成。

基本的伪代码如下：

void Unweighted(Table T){    for(int currDist = 0; currDist < NumVertex; ++currDist)    {        for each vertex V            if(!T[V].Known && T[V].Dits == currDist){                T[V].Known = true;                for each W adjacent to V                    if(T[W].Dist == Infinity){                        T[W].Dist = currDist + 1;                        T[W].Path = V;                    }            }    }}

上述算法把距离d=0上的顶点声明为Known，然后声明d=1上的顶点为Known，然后再声明d=2上的顶点为Known,以此类推，并将仍然是dc = x的所有邻接点的距离dv设置为d+1。通过追溯pv变量，我们可以显示实际路径。

但上述代码是双for循环，效率很低。

优化的伪代码如下：

void Unweighted(Table T){    Queue Q;    Vertex V, W;    Q = CreateQueue(NumVertex);MakeEmpty(Q);    Enqueue(S, Q);    while (!IsEmpty(Q)){        V = Dequeue(Q);        T[V].Known = True;        for each W adjancent to V:            if(T[W].Dist == Infinity){                T[W].Dist = T[V].Dist + 1;                T[W].Path = V;                Equeue(W, Q);            }    }    DisposeQueue(Q);}

如据变化过程