为了计算有向带权图中一个顶点到其他所有顶点的最短路径，其图的表示方法与最小生成树中的表示方法相同。只是用PathVertex结构体取代顶点MstVertex结构。
PathVertex能够表示带树图，同时能够追踪Dijkstra算法所需要的顶点和边的信息。此结构体包含5个成员：data是与顶点相关的数据；weight是到达该顶点的边的权值；color是顶点的颜色；d是顶点的最短路径估计；parent是最短路径中顶点的交结点。
构造一个包含pathvertex结构体的图的过程与构造一个包含MstVertex结构体的图的过程相同。
shortest操作首先初始化邻接表结构链表中的每个顶点。将每个顶点的最短路径估计初始化为DBL_MAX（起始顶点除外，起始顶点的初始值为0.0）。用存储在邻接表结构链表中的顶点来维护顶点的色值、最短路径估计和父结点。其原因与计算最小生成树时的解释相同。
Dijkstra算法的核心是用一个单循环为图中的每个结点迭代一次。在每次的迭代过程中，首先在所选的白色顶点中选择最短路径估计最小的顶点。同时，在邻接表结构链表中将此顶点涂黑。接下来，遍历与所选顶点相邻的顶点。在遍历每个顶点时，检查它在邻接表结构链表中的颜色和最短路径估计。一旦获得了这些信息，就调用relax释放所选顶点与相邻顶点间的边。如果此过程中发现需要更新相邻顶点的最短路径估计和父结点，那么就在邻接表结构链表中更新此顶点。重复这个过程直到所有顶点都涂成黑色。
一旦Dijkstra算法中的主循环结束，计算图中起始顶点到所有其他顶点的最短路径的过程也就完成了。此时，将邻接表结构链表中每个黑色的PathVertex结构体插入链表paths中。在paths中，父结点为NULL的顶点就是起始顶点。其他每个顶点的parent成员都指向从起始顶点开始的最短路径中的前一个顶点。每个PathVertex结构体的成员weight并不经常使用，因为它只在存储到邻接表中时才用的到。下图展示了在上图1中计算最短路径时所返回的PathVertex结构体列表。
/*shortest.c*/ #include <float.h> #include <stdlib.h> #include "graph.h" #include "graphalg.h" #include "list.h" #include "set.h" /*relax 释放边、更新最短路径估计值、更新父结点*/ static void relax(PathVertex *u, PathVertex *v, double weight) { /*释放顶点u和v之间的边*/ if(v->d > u->d + weight) { v-> = u->d + weight; v->parent = u; } return; } /*shortest 最短路径计算函数*/ int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match)(const void *key1, const void key2)) { AdjList *adjlist; PathVertex *pth_vertex, *adj_vertex; ListElmt *element, member; double minimum; int found,i; /*初始化图中的所有顶点*/ found = 0; for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) { pth_Vertex = ((AdjList *)list_data(element))->vertex; if(match(pth_vertex, start)) { /*找到并初始化起始顶点*/ pth_vertex->color = white; pth_vertex->d = 0; pth_vertex->parent = NULL; found = 1; } else { /*非起始顶点，初始化*/ pth_vertex->color = white; pth_vertex->d = DBL_MAX; pth_vertex->parent = NULL; } } /*如果未匹配到起始顶点，程序退出*/ if(!found) return -1; /*使用Dijkstra算法计算从起始顶点开始的最短路径*/ i=0; while(i < graph_vcount(graph)) { /*从所有的白色顶点中，选择最短路径估计值最小的顶点*/ minimum = DBL_MAX; for(element=list_head(&graph_adjlists(graph)); element!=NULL; element = list_next(element)) { pth_vertex = ((AdjList*)list_data(element))->vertex; if(pth_vertex->color == white && pth_vertex->d < minimum) { minimum = pth_vertex->d; adjlist = list_data(element); } } /*将该顶点涂成黑色*/ ((PathVertex *)adjlist->vertex)->color = black; /*遍历与所选顶点相邻的顶点*/ for(member=list_head(&adjlist->adjacent); member != NULL; member = list_next(member)) { adj_vertex = list_data(member); for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) { pth_vertex = ((AdjList *)list_data(element))->vertex; if(match(pth_vertex, adj_vertex)) { relax(adjlist->vertex, pth_vertex, adj_vertex->weight); } } } i++; } /*将邻接表结构链表中每个黑色PathVertexx结构体插入链表paths中*/ list_init(paths,NULL); for(element=list_head(&graph_adjlists(graph)); element!=NULL; element=list_next(paths,NULL)) { /*加载邻接表结构链表中的每一个黑色顶点*/ pth_vertex=((AdjList *)list_data(element))->vertex; if(pth_vertex->color == black) { if(list_ins_next(paths, list_tali(paths), pth_vertex) != 0) { list_destroy(paths); return -1; } } } return 0; }