没有合适的资源?快使用搜索试试~ 我知道了~
首页二重扫除算法:求解K条最短路径详解
二重扫除算法:求解K条最短路径详解
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 136 浏览量
更新于2024-07-04
收藏 232KB DOC 举报
"第K条最短路径算法文档详细探讨了在实际问题中对多条最短路径需求的情况,特别是在通信网络中备用线路的选择。这种问题被称为K最短路问题,解决此类问题的关键在于二重扫除算法,也称作双向扫除算法。算法的核心概念包括两类推广运算:推广的求极小值运算和推广的加法运算。 推广的求极小值运算定义为,对于两个向量A和B,它们的和A+B是通过取前k个元素的最小值来计算的。例如,如果A=(1, 3, 4, 8)和B=(3, 5, 7, 16),那么A+B=(1, 3, 4, 5)。推广的加法则是对每个对应位置的元素求和后,取前k个最小和,如A×B={(4, 6, 7, 8)}。 算法的核心步骤包括前向扫除和后向扫除。前向扫除是根据顶点编号的递增顺序,检查每个相邻顶点i是否可以提供更短的路径到达目标顶点j,如果有,更新路径估计值。这一步是逐个查找可能的K条最短路径。 双重扫除算法的整体迭代过程包含了这两个子过程,通过不断更新路径估计值,直到找到满足条件的第K条最短路径。值得注意的是,算法中对向量的定义有特定要求,如元素递增排序且取不同数值(除了∞),以及运算结果也需符合这些规则。例如,向量A=(-4, 0, 7, ∞)或B=(3, 4, ∞, ∞)是可以接受的,但像A=(-4, 3, 3, 9)和B=(-9, 0, ∞, 9)这样的组合因为元素重复或违反排序规则是不可接受的。 总结来说,第K条最短路径算法是解决多目标路径问题的有效工具,通过二重扫除方法,能够找出并排序出最短路径中的前K条,这对于通信网络中的故障恢复策略具有重要意义。理解并掌握这个算法,可以帮助我们在实际工程应用中做出快速、准确的决策。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/85301457/bg6.jpg)
#pragma pack(1)
using namespace std;
//实现二分查找功能
template <typename type_key>
size_t binaryFind(type_key *begin,type_key *end,const type_key &value)
{
if(begin> =end) return end-begin;
//unsigned __int64 size = sizeof(type_key);
//long len = (end-begin);
int total = (end-begin);
int low=0;
int high=total-1;
int mid=0;
unsigned __int64 temp = 0;
while(low <=high)
{
mid = (low+high)/2;
temp = *(begin+mid);
if(temp==value)
{
return mid;
}
if(temp> value)
{
high=mid-1;
continue;
}
else
{
low=mid+1;
continue;
}
}
return total;
}
//完成将 DocID 转换成 Index 的过程,以后每次迭代不用再进行查找,算是中间的辅助函数
unsigned int BuildIndex(FILE * mapFile)
{
cout < < "start to build index " < <endl;
FILE *countFile = fopen( "count.dat ", "rb ");
![](https://csdnimg.cn/release/download_crawler_static/85301457/bg7.jpg)
if (countFile==NULL)
{
cout < < "count.dat can not open,please check the 9le " < <endl;
return 0;
}
unsigned int total;
unsigned int MaxOutDegree;
fread(&total,4,1,countFile);
fread(&MaxOutDegree,4,1,countFile);
fclose(countFile);
cout < < "total is :/t " < <total < < "/tand the MaxOutDegree: " < <MaxOutDegree
< <endl;
if (total> 0)
{
unsigned __int64 *index = new unsigned __int64[total];
char *sons = new char[MaxOutDegree*(LENGTHOFSINGLE+1)];
FILE *indexMap = fopen( "indexMap.dat ", "wb ");
FILE *DocIDIndex = fopen( "DocID.index ", "wb ");
unsigned __int64 DocID;
int outDegree;
for(size_t i=0;i <total;++i)
{
fread(index+i,LENGTHOFSINGLE,1,mapFile);
fread(&outDegree,4,1,mapFile);
fread(sons,LENGTHOFSINGLE+1,outDegree,mapFile);
}
cout < < "end of read 9le " < <endl;
fwrite(index,LENGTHOFSINGLE,total,DocIDIndex);
rewind(mapFile);
size_t position;
for(size_t i=0;i <total;++i)
{
fread(&DocID,LENGTHOFSINGLE,1,mapFile);
fread(&outDegree,4,1,mapFile);
fread(sons,LENGTHOFSINGLE+1,outDegree,mapFile);
fwrite(&i,4,1,indexMap);
fwrite(&outDegree,4,1,indexMap);
for (int j=0;j <outDegree;++j)
{
//fread(sons,LENGTHOFSINGLE+1,1,mapFile);
剩余30页未读,继续阅读
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
老帽爬新坡
- 粉丝: 87
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)