Menu-driven dynamic, undirected weighted graph in C++: add/remove vertices and edges at runtime and compute shortest paths using Dijkstra’s algorithm (implemented with a linear scan, i.e., O(V²); no STL priority queue).
- Adjacency list graph with labeled vertices and weighted edges.
- Add/remove vertices and edges with input validation (no self-loops, no duplicate edges).
- Dijkstra’s algorithm via manual min-selection (clarity over speed), plus path reconstruction.
- Simple CLI menu for interactive updates and queries.
- Clean separation of interface and implementation (
GraphBase,Graph,main).
├── GraphBase.hpp # Abstract graph interface (add/remove/query APIs) GraphBase
├── Graph.hpp # Concrete graph (adjacency list, helpers, Dijkstra)
├── Graph.cpp # Implementation of graph ops + O(V²) Dijkstra
├── main.cpp # Menu-driven CLI (add/remove/shortest path/print)
├── COP_4530_Project_Report_.pdf # Design & results write-up
└── COP4530 Presentation.pdf # Slide deck overview
g++ -std=c++17 -Wall main.cpp Graph.cpp -o graphRun
./graph
You’ll see a menu to add/remove vertices/edges, compute shortest paths, and print the graph.
main🧠 Algorithm Notes
-
Dijkstra is implemented with a linear scan to pick the next vertex (no STL priority queue), making it O(V² + E) and ideal for small/teaching graphs.
-
Path is reconstructed by walking back using a prev vector.
🛠️ Example Operations
Add Vertex → creates a labeled node if it doesn’t exist.
Add Edge → adds an undirected weighted link (both directions).
Compute Shortest Path → prints path and total cost or “no path”.
✍️ Author
Daud Ahmad Nisar
Computer Science Student at the University of South Florida