equal
deleted
inserted
replaced
390 void init() { |
390 void init() { |
391 create_maps(); |
391 create_maps(); |
392 for (NodeIt it(*graph); it != INVALID; ++it) { |
392 for (NodeIt it(*graph); it != INVALID; ++it) { |
393 for (NodeIt jt(*graph); jt != INVALID; ++jt) { |
393 for (NodeIt jt(*graph); jt != INVALID; ++jt) { |
394 _pred->set(it, jt, INVALID); |
394 _pred->set(it, jt, INVALID); |
395 _dist->set(it, jt, it == jt ? |
395 _dist->set(it, jt, OperationTraits::infinity()); |
396 OperationTraits::zero() : OperationTraits::infinity()); |
|
397 } |
396 } |
|
397 _dist->set(it, it, OperationTraits::zero()); |
398 } |
398 } |
399 for (EdgeIt it(*graph); it != INVALID; ++it) { |
399 for (EdgeIt it(*graph); it != INVALID; ++it) { |
400 Node source = graph->source(it); |
400 Node source = graph->source(it); |
401 Node target = graph->target(it); |
401 Node target = graph->target(it); |
402 if (OperationTraits::less((*length)[it], (*_dist)(source, target))) { |
402 if (OperationTraits::less((*length)[it], (*_dist)(source, target))) { |
424 _pred->set(it, jt, (*_pred)(kt, jt)); |
424 _pred->set(it, jt, (*_pred)(kt, jt)); |
425 } |
425 } |
426 } |
426 } |
427 } |
427 } |
428 } |
428 } |
|
429 } |
|
430 |
|
431 /// \brief Executes the algorithm and checks the negative circles. |
|
432 /// |
|
433 /// This method runs the %FloydWarshall algorithm in order to compute |
|
434 /// the shortest path to each node pairs. If there is a negative circle |
|
435 /// in the graph it gives back false. |
|
436 /// The algorithm computes |
|
437 /// - The shortest path tree for each node. |
|
438 /// - The distance between each node pairs. |
|
439 bool checkedStart() { |
|
440 start(); |
|
441 for (NodeIt it(*graph); it != INVALID; ++it) { |
|
442 if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) { |
|
443 return false; |
|
444 } |
|
445 } |
|
446 return true; |
429 } |
447 } |
430 |
448 |
431 /// \brief Runs %FloydWarshall algorithm. |
449 /// \brief Runs %FloydWarshall algorithm. |
432 /// |
450 /// |
433 /// This method runs the %FloydWarshall algorithm from a each node |
451 /// This method runs the %FloydWarshall algorithm from a each node |