//贪心法解决单源最短路经问题
//定点v表示源,a为图的邻接矩阵,dist[i]表示源到顶点i的最短路经长度
//prev[i]表示最短路经中i顶点的前驱顶点
#define MAX_DISTANCE 100000
void Shortest_Path(int v,float **a,float dist[],int prev[],int n){
if(v < 1 || v > n) return;
bool *s = ( bool* )malloc( n * sizeof(bool) );//记录是否为s集合中的
//元素
for(int i = 0; i < n; i++)//初始化
{
dist[i] = a[v][i];
s[i] = false;
if(dist[i] < MAX_DISTANCE)
prev[i] = v;
else
prev[i] = 0;
}
dist[v] = 0;
s[v] = true;
for(int i = 0; i < n; i++) {
float temp = MAX_DISTANCE;
int u = v;
for(int j = 0; j < n; j++)//选择s集合外元素中到源v最小的顶点,并记录
//该点和最小值
{
if(!s[j] && dist[j] < temp)
{
u = j;
temp = dist[j];
}
}
s[u] = true;//将u加入s集合
for(int j = 0; j < n; j++) //更新dist的值,使dist[i]为当前的最优解
{
if(!s[j] && a[u][j] < MAX_DISTANCE)
{
float newdist = dist[u] + a[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
分享到:
相关推荐
单源最短路径--分支限界法
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
关于单源最短路径的问题非常典型,这里没有给出分析与证明,仅仅给出了实现。 需要指出的是,许多实现仅给出了最短路径的长度,而没有给出“最短路径”,这里用给出了实现。 如程序中那样,定义一个数组p[N],其中...
用C++实现的贪心算法 Dijkstra 单源最短路径,并包含大量的注释,对理解程序很有帮助
A、掌握图中单源最短路径的概念; B、掌握Dijkstra算法的原理;
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个整数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权...这个问题通常称为单源最短路径问题。
使用贪心算法实现单源点最短路径问题,C语言实现
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
1.分支限界法求解单源最短路径 2.C++源码+程序说明文档 3.源码带详细注释
经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径
基于贪心法求解单源最短路径问题 完整实验报告,结尾有实验代码
单元最短路径,为广大计算机专业学生算法所需实验报告而准备
图论算法库 C++ 语言实现 代码内容 图论算法库,包括以下算法: 单源最短路径 Dijkstra 算法 单源最短路径 Bellman-Ford 算法 最小生成树 Prim 算法 每对节点间最短路径 Flod-Warshall 算法
问题背景Dijkstra算法可以求解单源最短路径中国大学MOOC中国大学MOOC中国大学MOOC中国大学MOOC中国大学MOOC中国大学MOOC中国大学MOOC
有很长时间没有上传了,主要是因为这些天出了些小事。这个是用分支限界法求解单源最短路径问题的算法。
用Dijkstra算法实现单源最短路径问题。 第一行:n。代表n个顶点。其中第一个顶点为源点 第二行:c11 c12 c13....c1n (以下n行合起来为n*n的权矩阵,cij代表了i点到j点的边的权值,-1代表无穷大.每行n个数,数与...
单源最短路径C语言实现,简单易懂,适合算法学习
用python实现迪杰斯特拉算法,单源最短路径,有向图权值无负值,用邻接矩阵来存储有向图,实现路径存储和路径打印
分支限界法 (1)描述:采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。 所谓“分支”是采用广度优先的策略,依次生成扩展结点的所有分支(即:儿子结点)。 所谓“限界”是在结点扩展...
算法这么课程的结课论文,以最短路径算法为例描述贪心算法