迪杰斯特拉算法的具体应用

fill与memset的区别介绍

例一

在这里插入图片描述

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=500;
const int INF=1000000000;
bool isin[maxn]={false};
int G[maxn][maxn];
int path[maxn],rescue[maxn],num[maxn];
int weight[maxn];
int citynum,roadnum,begins,e;

void Dijisktra(int a){
    fill(path,path+maxn,INF);//记录最短距离
    memset(rescue,0,sizeof(rescue));//记录点权
    memset(num,0,sizeof(num));//记录最短路径的条数
    path[a]=0;
    rescue[a]=weight[a];
    num[a]=1;
    for(int i=0;i<citynum;i++){
        int pi=-1,pv=INF;
        for(int j=0;j<citynum;j++){
            //找最短距离的结点
            if(isin[j]==false&&path[j]<pv){
                pi=j;
                pv=path[j];
            }
     }
        if(pi==-1) return;
        isin[pi]=true;
        for(int k=0;k<citynum;k++){
            if(isin[k]==false&&G[pi][k]!=INF)
            {
                if(G[pi][k]+path[pi]<path[k])
                {
                    path[k]=G[pi][k]+path[pi];
                    num[k]=num[pi];//更新最短路径数：不相同就覆盖
                    rescue[k]=rescue[pi]+weight[k];
                }else 
                if(G[pi][k]+path[pi]==path[k]){
                    if(rescue[pi]+weight[k]>rescue[k])
                    rescue[k]=rescue[pi]+weight[k];//存大值
                    num[k]+=num[pi];//最短路径条数之和：相同累加
                }
            }
        }
    }
}
int main(){
    int v1,v2;//顶点及边权-距离
    fill(G[0],G[0]+maxn*maxn,INF);
    cin>>citynum>>roadnum>>begins>>e;
    for(int i=0;i<citynum;i++){
        cin>>weight[i];//记录点权-救援小组数目
    }
    for(int j=0;j<roadnum;j++){
        cin>>v1>>v2>>G[v1][v2];
        //建立无向图
        G[v2][v1]=G[v1][v2];
    }
    Dijisktra(begins);
    cout<<num[e]<<" "<<rescue[e];
    return 0;
}

例二

在这里插入图片描述
在这里插入图片描述

#include <iostream>
using namespace std;
const int maxn=100;
const int INF=1000000000;
bool isin[maxn]={false};
int G[maxn][maxn],expense[maxn][maxn];
int path[maxn],cost[maxn],pre[maxn];
int citynum,roadnum,b,e;

void Dijisktra(int a){//求最短路径
    fill(path,path+maxn,INF);
    fill(cost,cost+maxn,INF);
    path[a]=0;
    cost[a]=0;
    for(int i=0;i<citynum;i++) pre[i]=i;
    for(int i=0;i<citynum;i++){
        int m=-1,mv=INF;
        for(int j=0;j<citynum;j++){
            if(isin[j]==false&&path[j]<mv){
                m=j;
                mv=path[j];
            }
        }
        if(m==-1) return;
        isin[m]=true;
        for(int k=0;k<citynum;k++){
            if(isin[k]==false&&G[m][k]!=INF)
            {
                if(G[m][k]+path[m]<path[k]){
                    path[k]=G[m][k]+path[m];
                    cost[k]=expense[m][k]+cost[m];
                    pre[k]=m;
                }else if(G[m][k]+path[m]==path[k]){
                    if(cost[k]>expense[m][k]+cost[m])
                    cost[k]=expense[m][k]+cost[m];
                    pre[k]=m;
                }
            }
        }
    }
}
void DFSprint(int now){//打印
    if(now==b){
        cout<<now<<" ";
        return;
    }
    DFSprint(pre[now]);
    cout<<now<<" ";
}
int main(){
    int v1,v2;
    fill(G[0],G[0]+maxn*maxn,INF);
    fill(expense[0],expense[0]+maxn*maxn,INF);
    cin>>citynum>>roadnum>>b>>e;
    for(int i=0;i<roadnum;i++){
        cin>>v1>>v2>>G[v1][v2]>>expense[v1][v2];
        G[v2][v1]=G[v1][v2];
        expense[v2][v1]=expense[v1][v2];
    }
    Dijisktra(b);
    DFSprint(e);
    cout<<path[e]<<" "<<cost[e]<<endl;
    return 0;
}

拓展

用迪杰斯特拉+DFS求最短路径的方法
关键代码：

const int maxn=100;
const int INF=10000000000;
bool isin[maxn]={false};
int G[maxn][maxn],num;
int path[maxn],w[maxn];
vector<int> pre[maxn];//记录最短路径的前驱：考虑会有多个
vector<int> minPath,temPath;//只记录最优或当前路径

void Dijisktra(int a){
    fill(path,path+maxn,INF);
    path[a]=0;
    for(int i=0;i<num;i++){
        int m=-1,mv=INF;
        for(int j=0;j<num;j++){
            if(isin[j]==false&&path[j]<mv){
                m=j;
                mv=path[j];
            }
        }
        if(m==-1) return;
        isin[m]=true;
        for(int k=0;k<num;k++){
            if(isin[k]==false&&G[m][k]!=INF)
            {
                if(G[m][k]+path[m]<path[k]){
                    path[k]=G[m][k]+path[m];
                    //找到更优路径，清空，装最短的
                    pre[k].clear();
    //m结点加入k结点的前驱列表中，即为pre[k][i]==m;
                    pre[k].push_back(m);
                }else if(G[m][k]+path[m]==path[k]){
//此时有多条最短路径，即存在多个前驱结点，直接加入即可
                    pre[k].push_back(m);
                }
            }
        }
    }
}

void DFSprint(int now,int begins){
    int optValue=0;
    if(now==begins){
        temPath.push_back(begins);
        if(value>optValue){//更新最优
            optValue=value;
            minPath=temPath;
        }
        temPath.pop_back();//弹出第一个
        return;
    }
    temPath.push_back(now);
    for(int i=0;i<pre[now].size();i++){
        //遍历当前结点的前驱结点
        DFSprint(pre[now][i]);//不断递归now结点的前驱列表
    }
    temPath.pop_back();//依次弹出第二个.....
}
//计算边权和
int edge=0;
for(int i=temPath.size()-1;i>0;i--){
    int now=temPath[i],next=temPath[i-1];
    edge+=G[now][next];//计算边权
}
//计算点权和
int weight=0;
for(int i=temPath.size()-1;i>0;i--){
    int now=temPath[i];//当前结点下标
    weight+=w[now];
}

例二：Dijiskatra+DFS

#include <iostream>
#include <vector>
using namespace std;
const int maxn=100;
const int INF=100000000;
bool isin[maxn]={false};
int G[maxn][maxn],expense[maxn][maxn];
int path[maxn],minValue=INF;
vector<int> pre[maxn],temPath,minPath;
int citynum,roadnum,b,e;

void Dijisktra(int a){
    fill(path,path+maxn,INF);
    path[a]=0;
    for(int i=0;i<citynum;i++){
        int m=-1,mv=INF;
        for(int j=0;j<citynum;j++){
            if(isin[j]==false&&path[j]<mv){
                m=j;
                mv=path[j];
            }
        }
        if(m==-1) return;
        isin[m]=true;
        for(int k=0;k<citynum;k++){
            if(isin[k]==false&&G[m][k]!=INF){
                if(path[m]+G[m][k]<path[k]){
                    path[k]=path[m]+G[m][k];
                    pre[k].clear();
                    pre[k].push_back(m);
                }else if(path[m]+G[m][k]==path[k]){
                    pre[k].push_back(m);
                }
            }
        }
    }
}
void DFSprint(int now){
    int tempValue=0;
    if(now==b){
        temPath.push_back(now);
        for(int i=temPath.size()-1;i>0;i--){
            int v1=temPath[i],v2=temPath[i-1];
            tempValue+=expense[v1][v2];
        }
        if(tempValue<minValue){
            minValue=tempValue;
            minPath=temPath;
        }
        temPath.pop_back();//出队
    }
    temPath.push_back(now);
    for(int i=0;i<pre[now].size();i++){
        DFSprint(pre[now][i]);
    }
    temPath.pop_back();
}
int main(){
    int v1,v2;
    fill(G[0],G[0]+maxn*maxn,INF);
    fill(expense[0],expense[0]+maxn*maxn,INF);
    cin>>citynum>>roadnum>>b>>e;
    for(int i=0;i<roadnum;i++){
        cin>>v1>>v2>>G[v1][v2]>>expense[v1][v2];
        G[v2][v1]=G[v1][v2];
        expense[v2][v1]=expense[v1][v2];
    }
    Dijisktra(b);
    DFSprint(e);
    for(int i=minPath.size()-1;i>=0;i--)
    cout<<minPath[i]<<" ";
    cout<<path[e]<<" "<<minValue<<endl;
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/423210.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

011 Linux_线程概念与创建

011 Linux_线程概念与创建

前言 本文将会向你介绍线程的概念&#xff0c;以及线程是怎么被创建的 线程概念 一、进程是承担系统资源的基本实体&#xff0c;线程是cpu调度的基本单位 首先&#xff0c;地址空间在逻辑上相当于进程的资源窗口&#xff0c; 每个进程都有这样一个资源窗口。通过地址空间页…
阅读更多...
《热辣滚烫》：用坚持不懈开启逆境中的职场出路

《热辣滚烫》：用坚持不懈开启逆境中的职场出路

"你只活一次&#xff0c;所以被嘲笑也没有关系&#xff0c;想哭也没有关系&#xff0c;失败更没有关系。" “人生就像一场拳击赛&#xff0c;你站不起来&#xff0c;就永远不知道自己有多强” “命运只负责洗牌&#xff0c;出牌的永远是自己。” 在今年的贺岁档电影市…
阅读更多...
MySQL的21个SQL经验

MySQL的21个SQL经验

1. 写完SQL先explain查看执行计划（SQL性能优化） 日常开发写SQL的时候，尽量养成这个好习惯呀：写完SQL后，用explain分析一下，尤其注意走不走索引。 explain select userid,name,age from user where userid =10086 or age =18;2、操作delete或者update语句，加个limit(S…
阅读更多...
C++之stack

C++之stack

1、stack简介 stack是实现的一个先进后出&#xff0c;后进先出的容器。它只有一个出口&#xff0c;只能操作最顶端元素。 2、stack库函数 &#xff08;1&#xff09;push() //向栈压入一个元素 &#xff08;2&#xff09;pop() //移除栈顶元素 &#xff08;3…
阅读更多...
IO多路转接

IO多路转接

1.select 初识select 系统提供 select 函数来实现多路复用输入 / 输出模型 . select 系统调用是用来让我们的程序监视多个文件描述符的状态变化的 ; 程序会停在 select 这里等待&#xff0c;直到被监视的文件描述符有一个或多个发生了状态改变 ; select函数模型 select的函…
阅读更多...
LaTeX-设置表格大小

LaTeX-设置表格大小

文章目录 LaTeX-设置表格大小1.创建表格2.设置表格的宽度2.1控制表格每一列的宽度2.2控制整个表格的宽度 3.设置表格的外观4.LaTeX绘制三线表 LaTeX-设置表格大小 本文介绍了LaTeX如何设置表格的大小、改变表格的外观以及如何绘制三线表。 1.创建表格 在LaTeX中创建表很耗时…
阅读更多...
RocketMQ学习笔记一

RocketMQ学习笔记一

课程来源&#xff1a;002-MQ简介_哔哩哔哩_bilibili &#xff08;尚硅谷老雷&#xff0c;时长19h&#xff09; 第1章 RocketMQ概述 1. MQ是什么&#xff1f; 2. MQ用途有哪些&#xff1f; 限流削峰&#xff1b;异步解耦&#xff1b;数据收集。 3. 常见MQ产品有哪些&对比…
阅读更多...
10-Java装饰器模式 ( Decorator Pattern )

10-Java装饰器模式 ( Decorator Pattern )

Java装饰器模式 摘要实现范例 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其结构 装饰器模式创建了一个装饰类&#xff0c;用来包装原有的类&#xff0c;并在保持类方法签名完整性的前提下&#xff0c;提供…
阅读更多...
测试/测试开发八股——找大厂测试实习基础篇

测试/测试开发八股——找大厂测试实习基础篇

第一部分：基础概念 1. 软件测试是什么？ 在规定的条件下对一个产品或者程序进行操作，以发现程序错误，衡量软件质量，并对其是否能满足设计要求进行评估的过程。 软件测试工程师的任务 2. 软件测试工程师的任务 软件测试工程师主要工作是检查软件是否有bug、是否具有稳定…
阅读更多...
【深度学习笔记】计算机视觉——图像增广

【深度学习笔记】计算机视觉——图像增广

图像增广 sec_alexnet提到过大型数据集是成功应用深度神经网络的先决条件。 图像增广在对训练图像进行一系列的随机变化之后&#xff0c;生成相似但不同的训练样本&#xff0c;从而扩大了训练集的规模。 此外&#xff0c;应用图像增广的原因是&#xff0c;随机改变训练样本可以…
阅读更多...
Spring对IoC的实现

Spring对IoC的实现

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…
阅读更多...
GO-并发

GO-并发

1. 并发 有人把Go语言比作 21 世纪的C语言&#xff0c;第一是因为Go语言设计简单&#xff0c;第二则是因为 21 世纪最重要的就是并发程序设计&#xff0c;而 Go 从语言层面就支持并发。同时实现了自动垃圾回收机制。 先来了解一些概念&#xff1a; 进程/线程 进程是程序在操…
阅读更多...
Bootstrap的使用

Bootstrap的使用

目录 js的引入&#xff1a; 1.行内式 2.嵌入式 3.外链式 Bootstrap:的引入 注意事项&#xff1a; 条件注释语句&#xff1a; 栅格系统&#xff1a; 列嵌套&#xff1a; 列偏移&#xff1a; 列排序&#xff1a; 响应式工具&#xff1a; Bootstrap的字体图标的使用&a…
阅读更多...
探讨苹果 Vision Pro 的 AI 数字人形象问题

探讨苹果 Vision Pro 的 AI 数字人形象问题

Personas 的设计模糊性&#xff1a; 部分人认为这种模糊设计可能是出于安全考虑&#x1f6e1;️。安全角度&#xff1a;Personas 代表着你的 AI 数字形象&#xff0c;在创建时&#xff0c;它相当于你的 AVP&#xff08;生物识别扫描器的存在增加了冒充的难度&#xff09;。如果…
阅读更多...
mysql服务治理

mysql服务治理

一、性能监控指标和解决方案 1.QPS 一台 MySQL 数据库&#xff0c;大致处理能力的极限是&#xff0c;每秒一万条左右的简单 SQL&#xff0c;这里的“简单 SQL”&#xff0c;指的是类似于主键查询这种不需要遍历很多条记录的 SQL。 根据服务器的配置高低&#xff0c;可能低端…
阅读更多...
Java ZooKeeper-RocketMQ 面试题

Java ZooKeeper-RocketMQ 面试题

Java ZooKeeper-RocketMQ 面试题 前言1、谈谈你对ZooKeeper的理解 &#xff1f;2、Zookeeper的工作原理&#xff08;Zab协议&#xff09;3、谈谈你对分布式锁的理解&#xff0c;以及分布式锁的实现&#xff1f;4、 zookeeper 是如何保证事务的顺序一致性的&#xff1f;5、 zook…
阅读更多...
使用lnmp环境部署laravel框架需要注意的点

使用lnmp环境部署laravel框架需要注意的点

1&#xff0c;上传项目文件后&#xff0c;需要chmod -R 777 storage授予文件权限&#xff0c;不然会报错file_put_contents(/): failed to open stream: Permission denied。 如果后面还是报错没有权限的话&#xff0c;就执行ps -ef |grep php查询php运行用户。然后执行chown …
阅读更多...
STM32-ADC一步到位学习手册

STM32-ADC一步到位学习手册

1.按部就班陈述概念 ADC 是 Analog-to-Digital Converter 的缩写&#xff0c;指的是模拟/数字转换器。它将连续变量的模拟信号转换为离散的数字信号。在 STM32 中&#xff0c;ADC 具有高达 12 位的转换精度&#xff0c;有多达 18 个测量通道&#xff0c;其中 16 个为外部通道&…
阅读更多...
小朋友来自多少小区 - 华为OD统一考试(C卷)

小朋友来自多少小区 - 华为OD统一考试(C卷)

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 幼儿园组织活动&#xff0c;老师布置了一个任务&#xff1a; 每个小朋友去了解与自己同一个小区的小朋友还有几个。 我们将这些数量汇总到数组 garden 中。 请…
阅读更多...
gofly框架接口入参验证使用介绍

gofly框架接口入参验证使用介绍

接口传入的参数做相关性质验证是开发中较为常用&#xff0c;gofly框架内置校验工具&#xff0c;提供开发效率&#xff0c;开发接口简单调用即可实现验证&#xff0c;下面介绍gofly框架数据验证设计思路及使用方法。 gofly框架提供了功能强大、使用便捷、灵活易扩展的数据/表单…
阅读更多...
最新文章

Copyright @ 2022~2023