JKeeJ1e30's blog

By JKeeJ1e30, 13 years ago, translation, In English

Thanks for translation by RodionGork

Problem statement:
Given an oriented graph with N vertices and M edges we are to find all vertex pairs for which exists a path of infinitesimal weight. 

About 2 months ago I wrote an article in russian version on algorithm for this problem. After some more work and with the help of new idea provided by Narg, I created an improved version of the algorithm. Here is its description 

Step 1. Build condensation of the graph. For each of strongly connected components (SCC) check, whether it contains any loop of negative weight - if so, paint all vertices of this SCC black - otherwise paint them white. 

Now note that if any strongly connected component (SCC) contains a negative-weight loop, then any pair of vertices from this component have infinitesimal-length path between them, since when building a path for any pair we could enter negative-weight loop and reduce total weight to any value. 

Use Ford-Bellman algorithm for each of SCC to find out whether it contains negative-weight loop. 

Step 2. For each of vertices perform BFS from it. If some vertex B could be reached from given starting vertex A via path, containing any black intermediate vertex - then the vertex pair (A, B) is one of those we seek for. Remember it or print out. Working this way we could find out all such pairs. 

Time complexity, by steps, is O((N1 + N2 + ... + Nk)*M) = O(N*M) for condensation and Ford-Bellman and O(N*M) for BFS. Summary does not exceed O(N*M).

Memory: O(n + m).

There is the code

I've tested my algorithm against implementation of Floyd by Edward Davtyan. I performed testing for three kinds of graphs: containing almost full set of edges, containing about quarter of this amount of edges and containing only about 1/20 of full set of edges. 

There is the test generator

Results:

 n

 m

The types of edges(if the weights is only positive +, or some is negative -)

time of Floyd, ms

time of my algo, ms 

 100

9000 

+

38

 36

 100

9000 

48

 68

 200

39000 

263

160 

 200

39000 

280 

513 

 400

159000 

2080 

1224 

 400

159000 

2033 

4054 

 500

240000 

4043 

2336 

 500

240000 

3880 

7482 

 100

2500 

31 

93 

 100

2500 

47 

110 

 200

10000 

265 

125 

 200

10000 

276 

226 

 400

40000 

2068 

409 

 400

40000 

2028 

1096 

 500

62500 

4027 

701 

 500

62500 

3861 

2019 

 100

500 

29 

93 

 100

500 

37 

94 

 200

2000 

237 

105 

 200

2000 

265 

120 

 400

8000 

1968 

180 

 400

8000 

1954 

305 

 500

12500 

3902 

251 

 500

12500 

3766 

492 






























































Another results(there isn't Floyd because this tests is too big for Floyd)
 n m the type of edges time of my algo
 10002000  53
 10002000  282
 10005000  282
 10005000  512
 15005000  349
 15005000  785
 150010000  607
 150010000  1309
 300010000  968
 300010000  3415
 50005000  313
 50005000  309
 500020000  3137
 500020000  10482
  • Vote: I like it
  • -24
  • Vote: I do not like it