## Search found 4 matches

Fri Aug 22, 2003 3:49 am
Forum: Volume 104 (10400-10499)
Topic: 10449 - Traffic
Replies: 58
Views: 22129
Bellman-Ford is best for this problem, and the complexity is O(NE) when you detect an edge on a negative cycle in the Nth relaxation, it means that all vetices reachable from these two vetex (on this edge) can be reduce to -infinity, so after the Bellman, run a DFS for every negative vetex~ also che...
Tue Mar 11, 2003 7:17 am
Forum: Algorithms
Topic: minimum path covering
Replies: 6
Views: 4109
3x very much for the detailed explaination

Actually "Air Raid" is the problem I'm trying to solve, and I learned the solution from some guy, but I never code something I don't know why.

So another 3x to your help, I think I can code it now
Mon Mar 10, 2003 2:31 pm
Forum: Algorithms
Topic: minimum path covering
Replies: 6
Views: 4109
I am sorry I haven't explained my problem clearly. :oops: It maybe called : cover all the nodes in the graph with least paths, and the path can start at any node, and end at any node. But as I mentioned, the graph is acyclic, so you can never go back where you start out! 3x to your help:) , but I th...
Sun Mar 09, 2003 1:04 pm
Forum: Algorithms
Topic: minimum path covering
Replies: 6
Views: 4109

### minimum path covering

It's a acyclic graph (I don't know if it's suitable for genral graphs), and I wanna find the " minimum path cover ". It's said Bipartite Match can solve this problem, and the result is : node_count - max_match_count I just don't why :( , can Anybody know why give me some explainations, or just tell ...