最短路径
在解决网络路由的问题中, 寻找图中一个顶点到另一个顶点的最短路径或最小带权路径是非常重要的过程.
正式表述为, 给定一个有向带权图 G=(V,E), 顶点 s 到 V 中顶点 t 的最短路径为在 E 中边的集合 S 中连接 s 到 t 代价最小的路径.
当找到 S 时, 我们就解决了单对顶点最短路径问题. 要做到这一点, 实际上首先要解决更为一般的单源最短路径问题, 单源最短路径问题是解决单对顶点最短路径过程中的一部分. 在单源最短路径问题中, 计算从一个顶点 s 到其他与之相邻顶点之间的最短路径. 之所以要用这个方法解决此问题是因为没有其他更好的办法能用来解决单对顶点最短路径问题.
Dijkstra 算法
解决单源最短路径问题的方法之一就是 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));
- /*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;
- }
- /*route.c*/
- #include <stdlib.h>
- #include "graphalg.h"
- #include "list.h"
- #include "route.h"
- /*route*/
- int route(List *paths, PathVertex *destination, PathVertex **next, int (*match)(const void *key1, const void *key2))
- {
- PathVertex *temp,
- *parent;
- ListElmt *element;
- int found;
- /* 查找位于网关链表中的目的地址 */
- found = 0;
- for(element = list_head(paths); element != NULL; element = list_next(element))
- {
- if(match(list_data(element),destination))
- {
- temp = list_data(element);
- parent = ((PathVertex *)list_data(element))->parent;
- found = 1;
- break;
- }
- }
- /* 如未发现目标地址, 函数退出 */
- if(!found)
- return -1;
- /* 计算到目的地最短路径的下一个网关 */
- while(parent!=NULL)
- {
- temp = list_data(element);
- found = 0;
- for(element = list_head(paths); element != NULL; element = list_next(element))
- {
- if(match(list_data(element),parent))
- {
- parent = ((PathVertex *)list_data(element))->parent;
- found = 1;
- break;
- }
- }
- /* 如果目标不能到达, 函数退出 */
- if(!found)
- return -1;
- }
- *next = temp;
- return 0;
- }
来源: https://www.cnblogs.com/idreamo/p/9521605.html