| 252 | }; |
| 253 | |
| 254 | struct BellmanFordShortestPath : public ShortestPath { |
| 255 | BellmanFordShortestPath( |
| 256 | const GraphBase& g, |
| 257 | const std::vector<double>& edge_weights, |
| 258 | const std::vector<double>& node_weights, |
| 259 | bool reverse) |
| 260 | : ShortestPath(g, edge_weights, node_weights, reverse) {}; |
| 261 | virtual void find_from_start_node( |
| 262 | int64_t start_node_id, |
| 263 | std::vector<ShortestPathNode>& shortest) override { |
| 264 | bool has_changed = true; |
| 265 | for (int64_t iter = 0; (iter < g.num_nodes()) && has_changed; iter++) { |
| 266 | has_changed = bellman_ford_iter(shortest); |
| 267 | } |
| 268 | if (has_changed) { |
| 269 | throw std::runtime_error( |
| 270 | "BellmanFordShortestPath: detected negative-weight cycle in graph"); |
| 271 | } |
| 272 | }; |
| 273 | bool bellman_ford_iter(std::vector<ShortestPathNode>& shortest) { |
| 274 | auto has_changed = false; |
| 275 | for (int64_t edge_id = 0; edge_id < g.num_edges(); edge_id++) { |
| 276 | int64_t u, v; |
| 277 | double weight = (edgeWeights.empty() ? 0.0 : edgeWeights.at(edge_id)); |
| 278 | if (reverse) { |
| 279 | u = g.onode(edge_id); |
| 280 | v = g.inode(edge_id); |
| 281 | } else { |
| 282 | u = g.inode(edge_id); |
| 283 | v = g.onode(edge_id); |
| 284 | } |
| 285 | weight += (nodeWeights.empty() ? 0.0 : nodeWeights[v]); |
| 286 | if (shortest.at(u).dist + weight < shortest.at(v).dist) { |
| 287 | has_changed = true; |
| 288 | shortest.at(v).dist = shortest.at(u).dist + weight; |
| 289 | shortest.at(v).nodeId = u; |
| 290 | shortest.at(v).edgeId = edge_id; |
| 291 | } |
| 292 | } |
| 293 | return has_changed; |
| 294 | } |
| 295 | }; |
| 296 | |
| 297 | struct DijsktraShortestPath : public ShortestPath { |
| 298 | DijsktraShortestPath( |
nothing calls this directly
no outgoing calls
no test coverage detected