首页 > 编程语言 >C++实现的最短路径问题

C++实现的最短路径问题

时间:2024-08-27 21:21:28浏览次数:12  
标签:vector dist weight 实现 路径 C++ int 算法 edge

最短路径问题

最短路径问题是图论中的一个经典问题,旨在寻找从一个起点到一个终点的最短路径。最常见的算法包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。这些算法被广泛用于导航系统、网络路由等领域。

问题描述

  1. 输入: 一个加权图,表示图中各节点之间的连接和权重,以及一个起始节点。
  2. 输出: 从起始节点到其他所有节点的最短路径长度。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

class ShortestPath {
public:
    // Dijkstra算法实现(适用于非负权重图)
    vector<int> dijkstra(int n, vector<vector<pair<int, int>>> &graph, int start) {
        vector<int> dist(n, INT_MAX);
        dist[start] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();

            if (d > dist[u]) continue;

            for (auto &edge : graph[u]) {
                int v = edge.first;
                int weight = edge.second;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }

        return dist;
    }

    // Bellman-Ford算法实现(适用于有负权重的图)
    vector<int> bellmanFord(int n, vector<vector<pair<int, int>>> &graph, int start) {
        vector<int> dist(n, INT_MAX);
        dist[start] = 0;

        for (int i = 1; i < n; i++) {
            for (int u = 0; u < n; u++) {
                for (auto &edge : graph[u]) {
                    int v = edge.first;
                    int weight = edge.second;
                    if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                    }
                }
            }
        }

        // 检查是否存在负权重环
        for (int u = 0; u < n; u++) {
            for (auto &edge : graph[u]) {
                int v = edge.first;
                int weight = edge.second;
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    cout << "Graph contains a negative-weight cycle" << endl;
                    return {};
                }
            }
        }

        return dist;
    }
};

int main() {
    int n, m, start;
    cout << "Enter the number of vertices: ";
    cin >> n;

思路分析

类的设计

ShortestPath类封装了求解最短路径问题的两种常见算法:Dijkstra算法和Bellman-Ford算法。
这种设计使得两种算法可以独立实现和测试,并根据不同的图特性选择合适的算法。

Dijkstra算法

dijkstra()方法使用优先队列(最小堆)来高效地选择当前距离最短的节点,并更新其邻接节点的最短距离。
这种方法适用于没有负权重的图,时间复杂度为O(E log V),其中E为边的数量,V为顶点的数量。

Bellman-Ford算法

bellmanFord()方法适用于含有负权重的图,并且可以检测负权重环的存在。
算法的时间复杂度为O(V * E),在图的稠密度较高时效率较低,但在处理负权重时有其优势。

标签:vector,dist,weight,实现,路径,C++,int,算法,edge
From: https://blog.csdn.net/PeterClerk/article/details/141612954

相关文章

  • 实战案例四:异步实现爬虫
    爬虫pip3installaiohttpimportaiohttpimportasyncioasyncdeffetch(session,url):print("发送请求:",url)asyncwithsession.get(url,verify_ssl=False)asresponse:text=awaitresponse.text()print("得到结果:",......
  • 注解是如何实现的?
    注解是否支持继承不支持继承不能使用关键字extends来继承某个@interface,但注解在编译后,编译器会自动继承java.lang.annotation.Annotation接口.虽然反编译后发现注解继承了Annotation接口,但即使Java的接口可以实现多继承,但定义注解时依然无法使用extends关键字继承@interface。......
  • 网络地址转换(NAT)技术实现细节
    网络地址转换(NAT)是一种在IPv4网络中实现地址转换的技术,它允许一个局域网(LAN)使用一个公共IP地址与Internet通信。NAT技术的实现细节包括以下几个方面:静态NAT:静态NAT将内部私有IP地址与外部公共IP地址进行一对一的映射。这种映射关系在NAT设备上预先配置,并且是永久的。静态N......
  • 生动形象的解释计算机网络中隧道技术实现原理
    隧道技术是计算机网络中一种用于在不同网络之间传输数据的方法。隧道技术的实现原理可以类比于在现实生活中的地铁隧道系统。让我们通过一个生活中的例子来生动形象地解释隧道技术的实现原理。假设你现在在城市A,想要去很远的城市B。城市A和城市B之间有一座大山,无法直接穿越......
  • 如何使用 Bittly 实现 UDP 请求自动响应与处理
    在开发基于UDP的应用时,如果通信目标未就绪或者临时不可用时,可以使用Bittly的模拟服务虚拟一个支持UDP通讯的通讯终端。本文将介绍如何使用Bittly工具,实现对UDP请求的自动响应、动态数据处理、数据分帧以及数据转发。我们将从服务的准备工作开始,逐步讲解每一个步骤,帮......
  • C++系列学习笔记
    #include<iostream>#include<iomanip>usingnamespacestd;//namespace:命名空间的关键字//std:系统的关键字intmain(){cout<<"输入"<<endl<<"int,char,double"<<endl;intnum=0;ch......
  • 分析 HashSet 和 TreeSet 分别如何实现去重的
     分析HashSet和TreeSet分别如何实现去重的: (1)HashSet的去重机制:hashCode()+equals()。底层先通过存入对象,进行运算得到一个hash值,通过hash值得到对应的索引,如果发现table索引所在的位置,没有数据,就直接存放;如果有数据,就进行equals遍历比较,比较后不相同,就加入,否......
  • 生产者消费者模式,以及基于BlockingQueue的快速实现
    生产者消费者模式,以及基于BlockingQueue的快速实现什么是生产者消费者模式,简单来说就是有两个角色,一个角色主要负责生产数据,一个角色主要负责消费(使用)数据。那么生产者直接依赖消费者,然后直接调用是否可以?答案是可以的,但是有些场景无法及时解决,典型的就是生产者消费者的速度无法同......
  • 小米路由器刷入Breed与OpenWrt详细流程并实现远程管理本地软路由
    文章目录前言1.安装Python和需要的库2.使用OpenWRTInvasion破解路由器3.备份当前分区并刷入新的Breed4.安装cpolar内网穿透4.1注册账号4.2下载cpolar客户端4.3登录cpolarwebui管理界面4.4创建公网地址5.固定公网地址访问前言今天分享一下如何在小米路......
  • C语言字符函数和字符串函数的详解及模拟实现(超详细)
    目录1.求字符串长度1.1strlen1.1.1.strlen函数介绍1.1.2.strlen函数模拟实现 2.长度不受限制的字符串函数 2.1strcpy2.1.1.strcpy函数介绍2.1.2.strcpy函数模拟实现 2.2strcat2.2.1.strcat函数介绍2.2.2.strcat函数模拟实现 2.3strcmp 2.3.1.strcmp函数介绍......