I have a set of nodes AG, Z, with defined weighted edges, where AG are the various nodes in the funnel with Z at the very bottom.
Visualize a funnel (V-shaped) with different edges, but in the end point at Z, the final node, like water flowing down to one point Z. We want to find the cheapest path to Z that covers all the nodes in the sequence.
Here are the limitations:
- No orphan nodes (all nodes are connected / enabled)
- We want to minimize the sum of weighted edges
- “Sharing borders”, like pooling water when it flows down, only takes into account the total weight of the edge once (in other words, it can flow along a wet path).
Which accelerator graph algorithm should be used to find the optimal set of edges for this problem?
- ABDEZ is a cheap way that spans many nodes.
- CGZ is a bit forced since G has only one path to Z
- FZ looks cheap, but then we notice that since CGZ is forced, FGZ is actually cheaper than FZ (since we do not need to double the account of the GZ segment, the incremental cost of FG is only 1)
Thus, the set of edges must be (AB, BD, DE, EZ, CG, FG, GZ)
I am sure this is not a new problem: I just do not know enough graph theory to define / define an algorithm.
Update
When investigating the problem a few more, I found that if the graph is not directed , the problem boils down to the Minimal Spanning Tree . In other words, if we did not indicate a priori that Z is the lowest point on the graph (using arrows) and that water is allowed to flow in both directions (usually if we have valves), then this second model will work fine.
Of course, instead of forcibly using the old directional edge of the GZ , we can now select the new FZ non-oriented edge for less weight.
In light of these results, if we really need directional edges, liori answer is the best answer to the original question (i.e. the algorithm should be encoded).
Output
D <--> E with weight of 1 F <--> G with weight of 1 A <--> B with weight of 2 E <--> Z with weight of 2 C <--> G with weight of 2 F <--> Z with weight of 2 B <--> D with weight of 3 Total Weight = 13
Code for an undirected acyclic graph using a minimal spanning tree
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/kruskal_min_spanning_tree.hpp> #include <iostream> int main() { using namespace boost; typedef adjacency_list < vecS, vecS, undirectedS, no_property, property < edge_weight_t, int > > Graph; typedef graph_traits < Graph >::edge_descriptor Edge; typedef graph_traits < Graph >::vertex_descriptor Vertex; typedef std::pair<int, int> E; char letter[] = "ABCDEFGZ"; const int num_nodes = 8; E edge_array[] = { E(0,1), E(1,2), E(1,3), E(3,6), E(3,5), E(3,4), E(2,5), E(2,6), E(5,7), E(5,6), E(6,7), E(4,7) }; int weights[] = { 2, 6, 3, 5, 3, 1, 4, 2, 2, 1, 3, 2 }; std::size_t num_edges = sizeof(edge_array) / sizeof(E); Graph g(edge_array, edge_array + num_edges, weights, num_nodes); property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g); std::vector < Edge > spanning_tree; kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree)); int total_weight = 0; for (std::vector < Edge >::iterator ei = spanning_tree.begin(); ei != spanning_tree.end(); ++ei) { std::cout << letter[source(*ei, g)] << " <--> " << letter[target(*ei, g)] << " with weight of " << weight[*ei] << std::endl; total_weight += weight[*ei]; } std::cout << "Total Weight = " << total_weight << std::endl; return EXIT_SUCCESS; }