Skip to content

Latest commit

 

History

History
32 lines (25 loc) · 848 Bytes

README.md

File metadata and controls

32 lines (25 loc) · 848 Bytes
Raw

RSP Shortest Path Algorithms by RZN

Dependency

  • jbeder/yaml-cpp
  • For using <format>,
    • Above C++20 required
    • Not all compilers implements <format>

Data Structures

  • GraphBuilder converts yaml graph data in data/ to graph data.
  • IGraph is ADT of graph, use this interface to handle graphs without knowing specific implementation.
  • Currently only Graph_AdjacencyList implemented. (TODO)

Shortest Path Algorithms

  • Breadth First Search
  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
  • A*

Todos

  • Implement graph using adjacency list
  • Implement graph using adjacency matrix
  • Divide implementation for:
    • Single Pair
    • Single Source
    • Single Destination
    • All Pairs
  • Implement not only for path length, but returning path itself