CLRS-Cpp-Implementations-Chapter-24

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include "chapter-22/dfs_graph/dfs_graph.h"
#include "chapter-22/linked_list_graph/linked_list_graph.h"
#include "chapter-24/single_source_shortest_paths/sssp_utilities.h"
namespace CLRS
{
  void dag_shortest_paths
  (LinkedListGraph<SSSPDFSVertexGraph,
   SSSPWeightEdgeGraph<SSSPDFSVertexGraph>> &g,
   std::size_t s)
  {
    auto l = topological_sort_graph(g);
    initialize_single_source(g, s);
    for(std::size_t u : l)
      {
	for(const auto &ev : g.get_adj_vertexes(u))
	  sssp_relax(g, g.edgesr()[ev]);
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include "chapter-19/fibonacci_heap/fibonacci_heap.h"
#include "chapter-22/linked_list_graph/linked_list_graph.h"
#include "chapter-24/single_source_shortest_paths/sssp_utilities.h"
#include "chapter-23/minimum_spanning_tree/mst_utilities.h"
namespace CLRS
{
  void dijkstra
  (LinkedListGraph<DijkstraVertexGraph,
   WeightEdgeGraph<DijkstraVertexGraph>> &g,
   std::size_t s)
  {
    initialize_single_source(g, s);
    // fibonacci heap now contains all node of g
    auto fib_h =
      CLRS::make_fib_heap<DijkstraVertexGraph>();
    // have to create a graph node <-> shared_ptr index
    std::vector
      <std::shared_ptr
       <FibHeapTreeNode<DijkstraVertexGraph>>> vshr;
    for(std::size_t i = 0;
	i != g.get_vertexes_size();
	++i)
      {
	auto shr = std::make_shared
	  <FibHeapTreeNode
	   <DijkstraVertexGraph>>(g.vertex(i));
	vshr.push_back(shr);
	fib_heap_insert(fib_h, shr);
      }
    while(fib_h.get_n())
      {
	auto u = fib_heap_extract_min(fib_h);
	for(const auto &ev : g.get_adj_vertexes
	      (u->get_key().get_index()))
	  {
	    auto vr = sssp_relax(g, g.edgesr()[ev]);
	    auto v = vshr[g.edgesr()[ev].get_second_vertex()];
	    if(vr < v->get_key())
	      fib_heap_decrease_key(fib_h, v, vr);
	  }
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include "chapter-22/linked_list_graph/linked_list_graph.h"
#include "chapter-24/single_source_shortest_paths/sssp_utilities.h"
namespace CLRS
{
  bool bellman_ford
  (LinkedListGraph<SSSPVertexGraph,
   SSSPWeightEdgeGraph<SSSPVertexGraph>> &g,
   std::size_t s)
  {
    initialize_single_source(g, s);
    for(std::size_t i = 0;
	i != g.get_vertexes_size() - 1;
	++i)
      {
	for(const auto &e : g.get_edges())
	  sssp_relax(g, e);
      }
    for(const auto &e : g.get_edges())
      {
	std::size_t ui = e.get_first_vertex();
	std::size_t vi = e.get_second_vertex();
	auto u = g.vertex(ui);
	auto v = g.vertex(vi);
	if(v.is_dw_set() && u.is_dw_set())
	  {
	    if(v.get_dw() > (u.get_dw() + e.get_weight()))
	      return false;
	  }
      }
    return true;
  }
}