经过指定点的最短路径

这篇具有很好参考价值的文章主要介绍了经过指定点的最短路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

给出一个有 n 个顶点的有向网,指定其中 k 个顶点( 不含顶点 1 和顶点 n ),求从顶点 1 到顶点 n 的,经过那 k 个顶点的最短路。

输入:

第一行是 顶点数 n 和 弧数目 e 。 1 ≤ n ≤ 40 ,1 ≤ e ≤ n × n
接下来是 e 行,每行三个整数 i , j , v ( 其中 0 < i, j ≤ n , 0 < v ≤ 100 ) ,表示从 顶点 i 到 顶点 j 的一条权值为 v 的弧。
接下来是一个正整数 k ( 1 ≤ k ≤ n - 2 ),接下来是 k 个正整数,表示必须经过的 k 个顶点。

输出:

如果不存在满足条件的路径,输出一行 "No solution";
否则,输出两行:
第 1 行,该最短路的长度;
第 2 行从顶点 1 到顶点 n 的最短路,顶点之间用一个空格分隔,要求按路径的顶点次序,前一个顶点必须有弧指向后一个顶点

思路:暴力枚举所有满足条件的路径,计算路径长度并不断更新最短距离值。

算法实现:
1.跑一遍Floyd,求各顶点之间的最短路径
2.对所有指定点进行全排列,对每个排列计算:顶点1到序列首顶点的距离+序列中相邻顶点之间的距离+序列末顶点到顶点n的距离,并不断更新得到最短路径
3.特判不存在满足路径的情况

代码如下:

#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f //设无穷大值

int n, m, k, idx;
int dist[45][45];   //存储各顶点间的最短路
int path[45][45];   //用于floyd存储路径
int must[40];       //存储指定点序列
char temp[45], anspath[45];

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }                                  
}

//获取点a到点b最短路的中间路径(路径中不含a,b)
void getpath(int a, int b) {
    if (path[a][b] == -1)
        return;
    else {
        int k = path[a][b];
        getpath(a, k);
        anspath[idx++] = k;
        getpath(k, b);
    }
}

//将“点1沿着当前must数组中指定点的顺序走到点n的路径”保存到anspath数组
void savpath() {
    anspath[idx++] = 1;
    getpath(1, must[0]);
    for (int i = 0; i < k - 1; i++) {
        anspath[idx++] = must[i];
        getpath(must[i], must[i + 1]);
    }
    anspath[idx++] = must[k - 1];
    getpath(must[k - 1], n);
    anspath[idx++] = n;
}     

//返回 点1沿着当前must数组中指定点的顺序走到点n 的路径长度
int getdis() {
    int distance = dist[1][must[0]];
    if (dist[1][must[0]] == INF)
        return INF + 1;
    for (int i = 0; i < k - 1; i++) {
        if (dist[must[i]][must[i + 1]] == INF)
            return INF + 1;
        distance += dist[must[i]][must[i + 1]];
    }
    if (dist[must[k - 1]][n] == INF)
        return INF + 1;
    distance += dist[must[k - 1]][n];
    return distance;
}

int main() {

    memset(dist, 0x3f, sizeof dist);
    memset(path, -1, sizeof path);
    scanf("%d%d", &n, &m);

    int a, b, w;
    while (m--) {
        scanf("%d%d%d", &a, &b, &w);
        dist[a][b] = min(dist[a][b], w);
    }
    floyd();

    scanf("%d", &k);
    for (int i = 0; i < k; i++)
        scanf("%d", &must[i]);
    
    //判断点1能否走到点n
    if (dist[1][n] == INF) {
        printf("No solution\n");
        return 0;
    }

    //使用next_permutation函数前先对数组进行排序
    sort(must, must + k);
    int mindis = INF;
    do {
        int d = getdis();
        if (mindis > d) {//如果存在更短的路径则更新答案,并把路径存到anspath[]
            mindis = d;
            idx = 0;
            savpath();
        }
    } while (next_permutation(must, must + k));

    printf("%d\n", mindis);
    for (int i = 0; i < idx; i++)
        printf("%d ", anspath[i]);

    return 0;
}

本题的一个坑:使用dfs算法无法通过。

如果通过使用dfs算法记录所有点1到达点n并且经过指定点的路径,在其中取最小值并不正确。因为dfs算法要求路径中的点最多只出现一次,但经过指定点的最短路的路径中可能存在同一个点出现多次的情况,而这种情况恰好被dfs排除,因此本题不用dfs。

例:在如下图中,求点1经过点2,点3到达点4的最短路径和长度

必须经过某些点的最短路径,图论,最短路,算法,图论,c++,c语言

如果我们用dfs求解,得到的最短路径为:1->2->3->4,长度为420

而用暴力方法得到的最短路答案为:1->2->3->2->4,长度为40,其中点2在路径中出现过两次

显然,后者所求的最短路径正确文章来源地址https://www.toymoban.com/news/detail-604012.html

到了这里,关于经过指定点的最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 实验六 基于 Dijsktra 算法的最短路径求解

    实验六 基于Dijsktra算法的最短路径求解 一、实验目的 1.掌握图的邻接矩阵表示法,掌握采用邻接矩阵表示法创建图的算法。 2.掌握求解最短路径的 Dijsktra 算法。 二、实验内容 一张地图包括 n 个城市,假设城市间有 m 条路径(有向图),每条路径的长度 已知。给定地图的一个起

    2024年01月18日
    浏览(59)
  • matlab算法模型——图的最短路径和距离

    目录 一、前言 二、最短路径 1.sqarse创建稀疏矩阵 ​​2.有向图的最短路径         使用graphallshortestpaths函数 使用dijkstra.ma函数(直接引用) 3.无向图的最短路径 使用函数graphallshortestpaths(2021的版本不能用了) 使用shortestpath函数 三、未解决的问题 动态规划——求解某类问题

    2024年02月04日
    浏览(38)
  • 实验报告——基于Dijsktra算法的最短路径求解

    一个不知名大学生,江湖人称菜狗 original author: jacky Li Email : 3435673055@qq.com Last edited: 2022.12.3   目录 一、实验目的 二、实验设备 三、实验内容 【问题描述】 【输入要求】 【输出要求】 【输入样例】 【输出样例】 四、实验提示 五、实验步骤 5.1 六、实验结果 6.1程序完成后

    2024年02月07日
    浏览(48)
  • 算法课程设计--A*算法解决特定条件下的最短路径问题

             LOL 峡谷地图最优路径规划        以下问题的计算,按照该地图的基本规则来进行在该地图中分布着各种形状不规则的障碍区域环境。整个地图模型,可以根据需求进行自行简化。 问题一:在任意起点与终点之间,规划一条最短路径。 问题二:当你拥有一个闪现

    2024年02月10日
    浏览(60)
  • DS图—图的最短路径(无框架)迪杰斯特拉算法

    目录 题目描述 AC代码 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起,每行输入邻接矩阵的一行,以此类推输入n行 第i个结点与其它结点如果

    2023年04月08日
    浏览(41)
  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(48)
  • 数据结构实验任务六 :基于 Dijsktra 算法的最短路径求解

    本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文: 图论:Dijkstra算法——最详细的分析,图文并茂,一次看懂!-CSDN博客 以下附上实现代码: 以上代码仅供参考,欢迎交流。

    2024年02月04日
    浏览(50)
  • 详解图的最短路径算法(BFS、Dijkstra、Floyd)(附上图解步骤)

    最短路径分为两种: (1)单源路径:从某顶点出发,到其他全部顶点的最短路径 (2)顶点间的最短路径:任意两个顶点之间的最短路径 最短路径的结果主要有两个方面: (1)顶点之间最短路径的长度 (2)从源顶点到目标顶点的路径 只有边权为 1 时才能用BFS求最短路。

    2024年02月05日
    浏览(55)
  • 数据结构(12)Dijkstra算法JAVA版:图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径,即最少步数,使用BFS+贪心算法来求解最短路径,比较好实现,此处不做展开讨论。 有权图的最短路径,不考虑权重为负数的情况,因为权重为负

    2024年02月06日
    浏览(48)
  • C++语法09:迷宫中的最短路径:广度优先搜索算法的应用

    广搜,即广度优先搜索(Breadth-First Search, BFS),是图论和计算机科学中常用的一种算法。它从一个顶点开始,探索所有相邻的顶点,然后对每个相邻的顶点做同样的操作,直到找到目标顶点或遍历完所有顶点。广搜算法在实际应用中具有广泛的用途和诸多好处,本文将详细探

    2024年02月19日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包