单源最短路径(所谓单源最短路徑就是只指定一个顶点最短路径是指其他顶点和这个顶点之间的路径的权值的最小值)
给定一带权图,图中每条边的权值是非负的代表着两顶点之间的距离。指定图中的一顶点为源点找出源点到其它顶点的最短路径和其长度的问题,即是单源最短路径问题
求解单源朂短路径问题的常用方法是Dijkstra(迪杰斯特拉)算法。该算法使用的是贪心策略:每次都找出剩余顶点中与源点距离最近的一个顶点
带权图G=<V,E>,令S為已确定了最短路径顶点的集合则可用V-S表示剩余未确定最短路径顶点的集合。假设V0是源点则初始 S={V0}。用数组Distance表示源点V0到其余顶点的路径長度用数组pre[i]表示最短路径序列上顶点i的前一个顶点。初始时pre[i]都是源点的下标。接下来需重复两个步骤:
- 从当前Distance[i]找出最小的一个记录其下标v=i,源点V0到顶点Vv的最短路径即已确定把Vv加入S。
重复以上两个步骤直至所有顶点的最短路径都已找到。
需要指出Dijkstra算法求解的不仅昰带权有向图图,无向图也是可以的下面给出一个完整的带权有向图带权图的实例:
基于邻接矩阵存储的带权有向图网络的Dijkstra算法的简单實现:
//定义图结构,采用邻接矩阵存储形式 /*邻接矩阵对于带权有向图网络(带权的带权有向图图)其中存放的是权值*/ //Dijkstra算法实现(基于邻接矩阵存储的带权带权有向图图) //注意:下标表示结点 int count = 0; //用于记录访问过的结点数目,后面用于控制循环 //更新剩余的结点的前驱和最短距离 /*将上面找到的最短路径的结点作为起始点, *连到其他未访问过的结点上 *当比从最初结点到这个结点的路径短的时候, *就将上个结点作为前驱结點更新一下即可*/