在解决网络路由的问题中，寻找图中一个顶点到另一个顶点的最短路径或最小带权路径是非常重要的过程。
正式表述为，给定一个有向带权图G=(V,E)，顶点s到V中顶点t的最短路径为在E中边的集合S中连接s到t代价最小的路径。
当找到S时，我们就解决了单对顶点最短路径问题。要做到这一点，实际上首先要解决更为一般的单源最短路径问题，单源最短路径问题是解决单对顶点最短路径过程中的一部分。在单源最短路径问题中，计算从一个顶点s到其他与之相邻顶点之间的最短路径。之所以要用这个方法解决此问题是因为没有其他更好的办法能用来解决单对顶点最短路径问题。
Dijkstra算法Dijkstra算法会生成一棵最短路径树，树的根为起始顶点s，树的分支为从顶点s到图G中所有其他顶点的最短路径。此算法要求图中所有的权值均为非负数。与Prim算法一样，Dijkstra算法也是一种利用贪心算法计算并最终能够产生最优结果的算法。
从根本上说，Dijkstra算法通过选择一个顶点，并不断地探索与此顶点相关的边，以此来确定每个顶点的最短路径最否是最优。此算法类似广度优先搜索算法，因为在往图中更深的顶点探寻之前首先要遍历与此顶点相关的所有顶点。为了计算s与其他所有顶点之前的最短路径，Dijkstra算法需要维护每个顶点的色值和最短路径估计。通常，最短路径估计由变量d表示。
开始，将所有色值设置为白色，最短路径估计设置为∞（代表一个足够大的数，大于图中所有边的权值）。将起始顶点的最短路径估计设置为0。随着算法的不断演进，在最短路径树中为每个顶点（除起始顶点）指派一个父结点。在算法结束之前，顶点的父结点可能会发生几次变化。
Dijkstra算法的运行过程如下：
首先，在图中所有白色顶点之间，选择最短路径估计值最小的顶点u。初始，最短路径估计值被设置为0的顶点将做为起始顶点。当选择此顶点后，将其涂成黑色。
接下来，对于每个与u相邻的顶点v，释放其边（u，v）。当释放边后，我们要确认是否要更新到目前为止所计算的最短路径。方法就是将（u，v）的权值加到u的最短路径估计中。如果这个合计值小于或等于v的最短路径估计，就将这个值指派给v，作为v的新最短路径估计。同时，将u设置为v的父结点。
重复这个过程，直到所有的顶点都标记为黑色。一旦计算完最短路径树，那么从s到另外一个顶点t的最短路径就能唯一确定：从树中t处的结点开始向随后的父结点查找，直到到达s。此寻找路径的反向路径即为s到t的最短路径。
下图展示了由a到图中其他顶点的最短路径的计算过程。例如，a到b的最短路径为（a，c，f，b），其权值为7。最短路径估计和每个顶点的父结点都显示在每个顶点的旁边。最短路径估计显示在斜线的左边，父结点显示在斜线的右边。浅灰色的边是最短路径树增长过程中的边。
shortest
int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match)(const void *key1, const void *key2));
返回值：如果计算最短路径成功，返回0；否则，返回-1。
描述：用于计算顶点start与有向带权图graph中其他所有顶点之间的最短路径。此操作会改变graph，所以如果有必要，在调用此操作之前先对图进行备份。
graph中的每个顶点必须包含PathVertex类型的数据。通过设置PathVertex结构体中的成员weight的值来指定每个边的权值，weitht的值由传入graph_ins_edge的参数data2决定。用PathVertex结构体的成员data来保存与顶点相关的数据，例如顶点的标识符。
graph的match函数（此函数在用graph_init对图进行初始化时调用）用来比较PathVertex结构体中的data成员。此函数与传入shortest中的参数match相同。
一旦计算完成，最短路径的相关信息将会返回给paths，paths是存储PathVertex结构体的列表。在paths中，起始顶点的父结点设置为NULL。而其他每个顶点的parents成员都指向位于该顶点之前的那个顶点，这个顶点位于从起始顶点开始的最短路径之上。paths中的顶点指向graph中的实际顶点，所以只要能够访问paths，函数调用都就必须要保证graph中的内存空间有效。一旦不再使用paths，就调用list_destroy来销毁paths。
复杂度：O（EV2），其中V是图中的顶点个数，E是边的条目数。
最短路径的实现与分析