使用的方法修改后的dijkstra算法，带有加权乘积
修改的bellman-ford算法，带有加权乘积
加权乘积的改进dijkstra算法在修改后的dijkstra算法中，我们首先将源节点的权重设置为无穷大，将所有其他节点的权重也设置为无穷大。在执行计算的过程中，我们不是用所有权重来更新距离，而是用到目前为止遇到的权重的乘积来更新它们。在每一步中，我们选择具有最小权重的节点，并以相同的方式更新其相邻节点的权重。这个过程一直持续到达目标节点。最终，沿着这条路径的权重乘积将表示最小可能值，满足权重大于或等于1的条件。
算法将所有中心权重初始化为无限大，除了源中心，其权重设置为0。
创建一个清除集合来跟踪已删除的节点。
当存在未访问的节点时，
选择未访问节点中权重最小的中心。
将所选中心标记为已访问。
对于每个未访问的相邻枢纽:
计算当前中心节点的权重和与之相连的边的权重。
如果计算出的项小于相邻中心的权重，则用计算出的乘积替换其权重。
重复步骤3，直到目标中心消失或所有中心都被访问。
目标中心的重量反映了从源头到目标点沿途最小的物品重量。
示例#include <bits/stdc++.h>using namespace std;// function to return the smallest product of edgesdouble 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 graphvoid addedge(vector<vector<pair<int, double>>>& graph, int u, int v, double weight){ graph[u].push_back({v, weight});}// function to print the graphvoid 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 codeint 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: 5graph: 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 algorithmdouble 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的边的最小乘积路径的详细内容。