Transport-Connectivity-in-SA

🌍 Transport Connectivity in Southern Africa

A C++ Graph Algorithms Project that models transport connections between major Southern African cities and demonstrates fundamental graph theory concepts:

• Adjacency Matrix Representation
• Breadth-First Search (BFS) Traversal
• Dijkstra’s Shortest Path Algorithm

---

🧠 Project Purpose

This project simulates a transport network where:

• Cities are nodes (vertices)
• Roads between cities are edges
• Distances (km) are edge weights

It demonstrates how graph algorithms are used in:

• Navigation systems
• Route optimization
• Transport planning
• Logistics systems

---

🗺 Cities Included

Index	City
0	Johannesburg
1	Windhoek
2	Gaborone
3	Harare
4	Maputo

---

🔗 Graph Representation

The transport network is stored using an Adjacency List:

```cpp vector<vector<pair<int, int»> adjacencyList Each pair represents:

{ destination_city_index, distance_in_km } Example:

{ {1, 1400}, {2, 350} } Means:

Johannesburg → Windhoek (1400 km)

Johannesburg → Gaborone (350 km)

📊 Features Implemented 1️ Adjacency Matrix Display Converts the adjacency list into a matrix format for easy visualization of distances between cities.

Example Output:

Adjacency Matrix (Distances in km) Johannesburg Windhoek Gaborone Harare Maputo Johannesburg 0 1400 350 0 0 Windhoek 1400 0 900 0 0 … 2️ Breadth-First Search (BFS) BFS explores the network level-by-level from a starting city.

✔ Shows connectivity ✔ Useful for discovering reachable cities

Example Traversal:

BFS Traversal starting from Johannesburg: Johannesburg -> Windhoek -> Gaborone -> Harare -> Maputo 3️ Dijkstra’s Shortest Path Algorithm Finds the shortest route between two cities using distance as weight.

✔ Uses a Min-Heap (priority queue) ✔ Guarantees optimal path for non-negative weights ✔ Time Complexity: O((V + E) log V)

Example Output:

Dijkstra’s Shortest Path from Johannesburg to Harare: Path: Johannesburg -> Gaborone -> Harare Total distance: 1300 km 🏗 Data Structures Used Structure Purpose vector<vector<pair<int,int»> Adjacency list graph vector Distance tracking vector Parent tracking for path reconstruction queue BFS traversal priority_queue Efficient Dijkstra processing ▶ How to Compile & Run Compile g++ main.cpp -o transport Run ./transport 🎓 Concepts Demonstrated Graph Theory

BFS Traversal

Dijkstra’s Algorithm

Path Reconstruction

Matrix vs List Representation

Real-World Applications Google Maps / GPS routing

Airline route planning

Logistics & supply chain optimization

Network routing

👨‍💻 Author Phumudzo Matshaya

🤖 AI Assistance AI tools were used to assist with:

Implementing Dijkstra’s algorithm using a priority queue

Formatting matrix output

This site is open source. Improve this page.