1.基本思想
从图的给定源点到其他各个顶点之间客观上应存在一条最短路径
,在这组最短路径中,按其长度的递增次序,依次求出到不同顶点的最短路径
和路径长度
即按长度递增的次序生成各顶点的最短路径,即先
求出长度最小的一条最短路径,然后求出长度第二小的
最短路径,依此类推,直到求出长度最长的最短路径.
2 算法思想说明
设给定 源点为 Vs,S为已求得最短路径的终点集,开始时令S={Vs} 。
当求得第一条最短路径(Vs ,Vi)后,S为{Vs,Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为 Vj,则,Vj只有:
◆ 源点到终点有直接的弧 <Vs,Vj>;
◆ 从Vs 出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。
即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。
若定义一个数组 dist[n],其每个dist[i]分量保存从 Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值,
则下一条最短路径的终点Vj必定是不在S中且值最小的顶点,即:
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条 最短路径
3.算法实现
设数组pre[n]保存从Vs到其他顶点的最短路径.若pre[i]=k,表示
从Vs到Vi的最短路径中,Vi的前一个顶点式Vk,
数组final[n],标示一个顶点是否加入 SAX2DTM
bool final[MAX_VEX];
int pre[MAX_VEX],dis[MAX_VEX];
void Dijkstra_path(AdjGraph *G,int v)
{
int j,k,m,min;
for(j=0;j<G->vexnum;j++)
{
pre[j]=v;final[j]=FALSE;
dist[j]=G->adj[v][j];
}/*各数组的初始化*/
dist[v]=0;final[v]=TRUE;/*设置S={v}*/
for(j=0;j<G->vexnum-1;j++)/*其余n-1个顶点*/
{
m=0;
while(final[m])m++;/*找不在S 中的顶点Vk*/
min=INFINITY;
for(k=0;k<G->vexnum;k++)
{
if(!final[k]&&dist[m]<min)
{min=dist[k];m=k;}
}/*求出当前最小的dist[k]值*/
final[m]=TRUE;/*将第k 个顶点并入S 中*/
for(j=0;j<G->vexnum;j++)
{if(!final[j]&&(dist[m]+G->adj[m][j]<distj]))
{
dist[j]=dist[m]+G->adj[m][j];
pre[j]=m;
}
}/*修改dist 和pre 数组的值*/
}/*找到最短路径*/
}
分享到:
相关推荐
使用贪心算法实现单源点最短路径问题,C语言实现
最短路径问题; 设计一个C程序,实现求解单源点最短路径问题;
* (有向)带权图的单源点最短路径算法 */ package dsa; public class BestFSDijkstra extends BestFS { //构造方法 public BestFSDijkstra(Graph g) { super(g); } //更新尚未访问的顶点到源点的最短距离 ...
NULL 博文链接:https://128kj.iteye.com/blog/1716609
可用mpi并行处理的单源点最短路径程序和数据集
单源最短路径问题存在一个简单算法,这个算法通称Dijk-stra算法,实际上只求出冲V0到G中所有其他结点的最短路径长度。
算法设计中的 单源点最短路径 Dijstra 方法 内附实验报告
求单源点最短路径效率很高的spfa算法,包括2个样例程序和测试数据。
单源点最短路径,最优二分检索树算法程序实现,包含设计文档和源代码
单源点最短路径算法的实现 数据结构 课程设计.pdf单源点最短路径算法的实现 数据结构 课程设计.pdf
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
struct Node { int distance; int prev; }; void PrintPath(Node* node, int source, int index) ... if (node[index].index == source) ...int BellmanFord(int** matrix, int node_num, int source, int dest) ...
系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,比如交通旅游、城市规划以及电网架设等等。系统性能稳定,适应性强,界面清晰,操作简单,适合用户使用。 课程...
经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径
1.分支限界法求解单源最短路径 2.C++源码+程序说明文档 3.源码带详细注释
单源最短路径--分支限界法
单元最短路径,为广大计算机专业学生算法所需实验报告而准备
算法设计与分析课内实验——动态规划求单源最短路径。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)