Previous part
- find with Dijkstra algo first shortest paths for whole graph
- find all cut-points in whole graph
- iterate over found shortest path - if current vertex is cut-point - we can run brute-force from previous cut-point till current
Results are crazy anyway - on the same test 7
- Yen: 13.86s, 29787, 3501 cycles
- Node Classification: 118.4s, 30013, 3501 cycles
- Postponed Node Classification: 104.95s, 30013, 3501 cycles
- PNC*: 120.33s, 30013, 3501 cycles
- Parsimonious Sidetrack Based: 4.66s, 29980, 3501 cycles
- Parsimonious Sidetrack Based v2: 4.79s, 29980, 3501 cycles
- Parsimonious Sidetrack Based v3: 4.85s, 29980, 3501 cycles
- Sidetrack Based: 4.18s, 29980, 3501 cycles
- Sidetrack Based with update: 4.34s, 29980, 3501 cycles
Source code