How can I select the starting path for the Edmonds-Karp algorithm if all the paths are the same length? In this case, maximum flow changes according to path sequence decision.
How to start Edmonds-Karp implementation if all the paths have same lengths?
1.3k Views Asked by Gary Leather At
1
There are 1 best solutions below
Related Questions in C++
- C++ using std::vector across boundaries
- Linked list without struct
- Connecting Signal QML to C++ (Qt5)
- how to get the reference of struct soap inherited in C++ Proxy/Service class
- Why we can't assign value to pointer
- Conversion of objects in c++
- shared_ptr: "is not a type" error
- C++ template using pointer and non pointer arguments in a QVector
- C++ SFML 2.2 vectors
- Lifetime of temporary objects
- I want to be able to use 4 different variables in a select statement in c ++
- segmentation fault: 11, extracting data in vector
- How to catch delay-import dll errors (missing dll or symbol) in MinGW(-w64)?
- How can I print all the values in this linked list inside a hash table?
- Configured TTL for A record(s) backing CNAME records
Related Questions in ALGORITHM
- Two different numbers in an array which their sum equals to a given value
- Given two arrays of positive numbers, re-arrange them to form a resulting array, resulting array contains the elements in the same given sequence
- Time complexity of the algorithm?
- Find a MST in O(V+E) Time in a Graph
- Why k and l for LSH used for approximate nearest neighbours?
- How to count the number of ways of choosing of k equal substrings from a List L(the list of All Substrings)
- Issues with reversing the linkedlist
- Finding first non-repeating number in integer array
- Finding average of an array
- How to check for duplicates with less time in a list over 9000 elements by python
- How to pick a number based on probability?
- Insertion Sort help in javascript -- Khan Academy
- Developing a Checkers (Draughts) engine, how to begin?
- Can Bellman-Ford algorithm be used to find shorthest path on a graph with only positive edges?
- What is the function for the KMP Failure Algorithm?
Related Questions in NETWORK-FLOW
- Find edge-disjoint paths (not the number, the paths)
- How to calculate maximum flow in a directed graph that contains cycles
- Network Flow Update Values
- Is this Sedgewick code correct?
- What algorithm should I use to find the minimum flow on a digraph where there are lower bounds but not upper bounds on flow?
- How do you find the maximum flow on a digraph where capacities may be negative?
- Loop over subset of variables in JuMP constraint
- In Push Relabel algorithms for max flow why is there not path from source s to sink t?
- The Integrality theorem in maximum flow
- my Minimum cost network flow cost in networkx takes a lot of time to be calculated
- how to use maximum network flow to solve this?
- how to use Network Flow to solve this?
- how to reduce Maximum cardinality bipartite matching to minimum path cover?
- how to use network flow to solve linear programming?
- setting the network algorithm in cplex but the solution was obtained with dual simplex
Related Questions in EDMONDS-KARP
- How do you find the maximum flow on a digraph where capacities may be negative?
- Update Maximum Flow After Adding an Edge
- Edmonds Karp algorithm and 0 1 capacities
- How to save last BFS of Edmonds-Karp algorithm?
- Why are the elements in my heapq not ordered python?
- How can I use the Edmonds & Karp Algorithm for residual graph
- Which assignment algorithm should I use?
- Using Named parameters and Bundled properties with edmonds_karp_max_flow()
- How to use custom edge implementation with EdmondsKarp max flow algorithm
- How to define cut set with Edmonds Karp Impl?
- An O(n * log(n)) algorithm for maximum st-flow in a directed planar graph (Borradaile, Klein)
- How to get flow for every edge using Jung's Edmonds Karp?
- How to get the cut-set using the Edmonds–Karp algorithm?
- Edmonds–Karp time complexity
- Why must back-edges be taken into account in Edmonds-Karp Maximum Flow?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
I think there is a problem with how you handle capacities at the vertices. The usual way this is done is by splitting the vertex v in two vertices v' and v'' and adding an edge between v' and v'' with the capacity of the vertex. All edges connected to v(i.e. for which v is destination) should be connected with v' in the new graph and all edges from v should start from v'' in the new graph.
You probably know that when you let flow x-a-b-y 3 you add to the capacity of the reverse edges. In that case you will add the edges a x 3, b a 3, y b 3. If you do the graph representation as I described you will see that there is additional flow you can use in the first case(I think it can pass through x-a-d-c-b-y, but have not checked it).
The selection of the shortest path should not change the answer - as I mentioned in my comment we only select the shortest path on each step to avoid bad cases where the performance suffers, but the answer is always the same.
Hope this answer helps.