目录
使用的方法
加权乘积的改进Dijkstra算法
算法
示例
输出
修改后的带加权乘积的Bellman-Ford算法
结论
首页 后端开发 C++ 具有权重大于等于1的边的最小乘积路径

具有权重大于等于1的边的最小乘积路径

Aug 30, 2023 am 11:37 AM
权重 路径

具有权重大于等于1的边的最小乘积路径

为了发现具有权重大于或等于1的最小边的路径,我们可以使用稍作修改的Dijkstra算法。首先,我们将源节点的权重设为1,将其他节点的权重设为无穷大。在算法执行过程中,我们不再更新距离,而是更新权重的乘积。这样可以确保选择具有最小权重的路径。通过在每一步选择权重最小的节点,我们迭代地发现最短路径,直到达到目标节点。最后,沿着这条路径的权重乘积将是最小的,满足给定的条件。

使用的方法

  • 修改后的Dijkstra算法,带有加权乘积

  • 修改的Bellman-Ford算法,带有加权乘积

加权乘积的改进Dijkstra算法

在修改后的Dijkstra算法中,我们首先将源节点的权重设置为无穷大,将所有其他节点的权重也设置为无穷大。在执行计算的过程中,我们不是用所有权重来更新距离,而是用到目前为止遇到的权重的乘积来更新它们。在每一步中,我们选择具有最小权重的节点,并以相同的方式更新其相邻节点的权重。这个过程一直持续到达目标节点。最终,沿着这条路径的权重乘积将表示最小可能值,满足权重大于或等于1的条件。

算法

  • 将所有中心权重初始化为无限大,除了源中心,其权重设置为0。

  • 创建一个清除集合来跟踪已删除的节点。

  • 当存在未访问的节点时,

    • 选择未访问节点中权重最小的中心。

    • 将所选中心标记为已访问。

    • 对于每个未访问的相邻枢纽:

    • 计算当前中心节点的权重和与之相连的边的权重。

    • 如果计算出的项小于相邻中心的权重,则用计算出的乘积替换其权重。

  • 重复步骤3,直到目标中心消失或所有中心都被访问。

  • 目标中心的重量反映了从源头到目标点沿途最小的物品重量。

示例

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

// Function to return the smallest product of edges
double modifiedDijkstra(int source, int destination, vector<vector<pair<int, double> > > graph)
{
    // If the source is equal to the destination
    if (source == destination)
        return 0;

    // Initialize the priority queue
    set<pair<double, int>> pq;
    pq.insert({1, source});

    // Visited array
    bool visited[graph.size()] = {0};

    // While the priority queue is not empty
    while (!pq.empty())
    {
        // Current node
        int current = pq.begin()->second;

        // Current product of weights
        double product = pq.begin()->first;

        // Pop the top-most element
        pq.erase(pq.begin());

        // If already visited, continue
        if (visited[current])
            continue;

        // Mark the node as visited
        visited[current] = true;

        // If it is a destination node
        if (current == destination)
            return product;

        // Traverse the neighbors of the current node
        for (auto neighbor : graph[current])
        {
            int neighborNode = neighbor.first;
            double weight = neighbor.second;

            // Calculate the product of weights
            double newProduct = product * weight;

            // Insert the new product and neighbor into the priority queue
            pq.insert({newProduct, neighborNode});
        }
    }

    // If no path exists
    return -1;
}

// Function to add an edge to the graph
void addEdge(vector<vector<pair<int, double>>>& graph, int u, int v, double weight)
{
    graph[u].push_back({v, weight});
}

// Function to print the graph
void printGraph(const vector<vector<pair<int, double>>>& graph)
{
    for (int i = 1; i < graph.size(); i++)
    {
        cout << "Node " << i << ": ";
        for (auto neighbor : graph[i])
        {
            cout << "(" << neighbor.first << ", " << neighbor.second << ") ";
        }
        cout << endl;
    }
}

// Driver code
int main()
{
    int numNodes = 3;

    // Graph as adjacency list
    vector<vector<pair<int, double>>> graph(numNodes + 1);

    // Input edges
    addEdge(graph, 1, 3, 9);
    addEdge(graph, 2, 3, 1);
    addEdge(graph, 1, 2, 5);

    // Source and destination
    int source = 1, destination = 3;

    // Modified Dijkstra
    double smallestProduct = modifiedDijkstra(source, destination, graph);

    // Print the result
    cout << "Smallest product of weights: " << smallestProduct << endl;

    // Print the graph
    cout << "Graph: " << endl;
    printGraph(graph);

    return 0;
}
登录后复制

输出

Smallest product of weights: 5
Graph: 
Node 1: (3, 9) (2, 5) 
Node 2: (3, 1) 
Node 3: 
登录后复制

修改后的带加权乘积的Bellman-Ford算法

在带有加权对象的调整后的Bellman-Ford算法中,我们通过将源中心的负载设置为1,将所有其他中心的负载设置为无穷大来开始。在每个循环中,通过比较当前节点的权重和连接它们到目标中心的边的负载来解开所有边。如果计算得到的权重比目标中心的负载小,我们将其权重增加计算得到的权重。重复这个过程V-1次,其中V是中心的总数,以确保考虑到所有可能的路径。目标中心的权重表示从源到目标的路径上最小的权重。

算法

  • 除了源中心之外,所有其他中心的权重应为无穷大。

  • 重复执行上述步骤 V−1 次,其中 V 是节点的总数:

    • 对于图表中的每条边,计算当前中心的项目权重以及与它们相连的边的权重。

    • 如果计算出的物品小于目标中心的重量,则用计算出的乘积升级其重量。

  • 经过V−1个周期,所有中心节点的权重将被确定。

  • 在计算过程中,如果图表中存在负权重循环,将会区分出一个额外的循环。如果在此过程中有任何权重被修正,这表明存在一个负权重循环的存在。

  • 目标中心的重量反映了从源头到目标点沿途最小的物品重量。

  • 贪婪着色算法基于可用颜色和邻居顶点使用的颜色,以贪婪的方式为顶点分配颜色。虽然它可能不总是使用最少数量的颜色来完成图表着色,但它提供了一种快速高效的顶点着色方法。

示例

#include <iostream>
#include <vector>
#include <limits>

struct Edge {
    int source, destination;
    double weight;
};

// Function to find the smallest product of weights using the modified Bellman-Ford algorithm
double findSmallestProduct(int numNodes, int source, int destination, std::vector<Edge>& edges) {
    std::vector<double> weights(numNodes, std::numeric_limits<double>::infinity());
    weights[source] = 1;

    for (int i = 1; i < numNodes; i++) {
        for (const auto& edge : edges) {
            double newWeight = weights[edge.source] * edge.weight;
            if (newWeight < weights[edge.destination]) {
                weights[edge.destination] = newWeight;
            }
        }
    }

    for (const auto& edge : edges) {
        double newWeight = weights[edge.source] * edge.weight;
        if (newWeight < weights[edge.destination]) {
            return -1.0; // Negative-weight cycle detected
        }
    }

    return weights[destination];
}

int main() {
    int numNodes = 4;

    std::vector<Edge> edges = {
        {0, 1, 2.0},
        {1, 2, 0.5},
        {2, 3, 1.5},
        {0, 3, 1.2},
        {1, 3, 0.8}
    };

    int source = 0, destination = 3;

    double smallestProduct = findSmallestProduct(numNodes, source, destination, edges);

    if (smallestProduct < std::numeric_limits<double>::infinity()) {
        std::cout << "The smallest product of weights along the path from node " << source
                  << " to node " << destination << " is: " << smallestProduct << std::endl;
    } else {
        std::cout << "A negative-weight cycle is detected. No valid path exists." << std::endl;
    }

    return 0;
}
登录后复制

输出

The smallest product of weights along the path from node 0 to node 3 is: 1.2
登录后复制

结论

本文阐明了如何找到具有权重大于或等于1的最小边的路径。它介绍了两个算法,即改进的Dijkstra算法和改进的Bellman-Ford算法,用于解决这个问题。改进的Dijkstra算法在每一步选择具有最小权重的节点,而改进的Bellman-Ford算法迭代地解开边以更新权重。文章提供了这两个算法在C语言中的实现,并用测试输入说明了它们的使用。输出结果是从源节点到目标节点的路径上的最小权重。

以上是具有权重大于等于1的边的最小乘积路径的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

主题背景位于 Windows 11 中的什么位置? 主题背景位于 Windows 11 中的什么位置? Aug 01, 2023 am 09:29 AM

Windows11具有如此多的自定义选项,包括一系列主题和壁纸。虽然这些主题以自己的方式是美学,但一些用户仍然想知道他们在Windows11上的后台位置。本指南将展示访问Windows11主题背景位置的不同方法。什么是Windows11默认主题背景?Windows11默认主题背景是一朵盛开的抽象宝蓝色花朵,背景为天蓝色。这种背景是最受欢迎的背景之一,这要归功于操作系统发布之前的预期。但是,操作系统还附带了一系列其他背景。因此,您可以随时更改Windows11桌面主题背景。主题背景存储在Windo

如何修复错误:在Java中找不到或加载主类 如何修复错误:在Java中找不到或加载主类 Oct 26, 2023 pm 11:17 PM

由于技术错误,无法播放此视频。(错误代码:102006)本指南提供了针对此常见问题的简单修复,并继续您的编码之旅。我们还将讨论Java错误的原因以及将来如何防止它。什么是Java中的“错误:找不到或加载主类”?Java是一种强大的编程语言,使开发人员能够创建广泛的应用程序。然而,它的多功能性和效率伴随着开发过程中可能发生的一系列常见错误。其中一个中断是错误:找不到或加载主类user_jvm_args.txt,当Java虚拟机(JVM)找不到主类来执行程序时会出现这种情况。此错误充当了障碍,甚至在

斜杠和反斜杠在文件路径中的不同使用 斜杠和反斜杠在文件路径中的不同使用 Feb 26, 2024 pm 04:36 PM

文件路径是操作系统中用于识别和定位文件或文件夹的字符串。在文件路径中,常见的有两种符号分隔路径,即正斜杠(/)和反斜杠()。这两个符号在不同的操作系统中有不同的使用方式和含义。正斜杠(/)是Unix和Linux系统中常用的路径分隔符。在这些系统中,文件路径是以根目录(/)为起始点,每个目录之间使用正斜杠进行分隔。例如,路径/home/user/Docume

Win11系统中'我的电脑”路径有何不同?快速查找方法! Win11系统中'我的电脑”路径有何不同?快速查找方法! Mar 29, 2024 pm 12:33 PM

Win11系统中“我的电脑”路径有何不同?快速查找方法!随着Windows系统的不断更新,最新的Windows11系统也带来了一些新的变化和功能。其中一个常见的问题是用户在Win11系统中找不到“我的电脑”的路径,这在之前的Windows系统中通常是很简单的操作。本文将介绍Win11系统中“我的电脑”的路径有何不同,以及快速查找的方法。在Windows1

如何查找Linux系统中RPM文件的存储路径? 如何查找Linux系统中RPM文件的存储路径? Mar 14, 2024 pm 04:42 PM

在Linux系统中,RPM(RedHatPackageManager)是一种常见的软件包管理工具,用于安装、升级和删除软件包。有时候我们需要找到某个已安装的RPM文件的存储路径,以便进行查找或者其他操作。下面将介绍在Linux系统中如何查找RPM文件的存储路径,同时提供具体的代码示例。首先,我们可以使用rpm命令来查找已安装的RPM包及其存储路径。打开

Python 3.x 中如何使用os.path模块获取文件路径的各个部分 Python 3.x 中如何使用os.path模块获取文件路径的各个部分 Jul 30, 2023 pm 02:57 PM

Python3.x中如何使用os.path模块获取文件路径的各个部分在日常的Python编程中,我们经常需要对文件路径进行操作,例如获取路径的文件名、文件目录、扩展名等等。在Python中,可以使用os.path模块来进行这些操作。本文将介绍如何使用os.path模块来获取文件路径的各个部分,以便更好地操作文件。os.path模块提供了一系

微博权重是什么意思 微博权重是什么意思 Dec 11, 2020 pm 02:36 PM

微博权重是指微博官方对微博号的评分,主要体现在搜索和评论时的排序,权重越高排序越靠前,因此微博权重也会影响到微博号的流量数据。提高权重可以通过实名制的方式,还可以成为微博的签约自媒体。

在JavaFX中,有哪些不同的路径元素? 在JavaFX中,有哪些不同的路径元素? Aug 28, 2023 pm 12:53 PM

javafx.scene.shape包提供了一些类,您可以使用它们绘制各种2D形状,但这些只是原始形状,如直线、圆形、多边形和椭圆形等等...因此,如果您想绘制复杂的自定义形状,您需要使用Path类。Path类Path类使用此表示形状的几何轮廓您可以绘制自定义路径。为了绘制自定义路径,JavaFX提供了各种路径元素,所有这些都可以作为javafx.scene.shape包中的类使用。LineTo-该类表示路径元素line。它可以帮助您从当前坐标到指定(新)坐标绘制一条直线。HlineTo-这是表

See all articles