Route Planning with Graph Algorithms is a Java-based mapping application that calculates and visualizes routes between geographic points using classical graph algorithms. Built as part of UCSD’s Advanced Data Structures in Java course on Coursera, this project demonstrates real-world graph theory applications via an interactive map interface powered by the Google Maps API.
- Features
- About the Project
- Getting Started
- Implementation Highlights
- Source Code Overview
- Contributing
- Credits
- License
- Support
- Compute shortest paths using Breadth-First Search (BFS), Dijkstra’s Algorithm, and A* Search
- Interactive route visualization on Google Maps
- Real-world road data integration with Java and JavaFX frontend
This project emphasizes algorithmic problem-solving through route planning, integrating backend graph logic with a frontend Google Maps interface. It’s a simplified but educational alternative to commercial mapping systems, focusing on algorithm design over production-grade UX.
- Implement graph structures and traversal algorithms from scratch in Java
- Understand trade-offs between different shortest path algorithms
- Visualize algorithm performance and pathfinding behavior in real geographic contexts
- Java 8 or higher – Download here
- Maven – Dependency and build manager (Install guide)
- Google Maps API Key – Get one here
- Eclipse IDE (optional) – or use any Java IDE of your choice
-
Clone the repository
git clone https://github.com/jitendrabhamare/UCSDGraphs.git
-
Navigate to the project directory
cd UCSDGraphs -
Set your Google Maps API key
Create the following file if it doesn't exist:
# File: src/main/resources/config.properties google.maps.api.key=YOUR_API_KEY
-
Build the project
mvn clean install
-
Launch the JavaFX application:
java -jar target/UCSDGraphs-1.0-SNAPSHOT.jar
-
Open
http://localhost:8080in your browser to interact with the map interface.
Custom MapGraph class represents the map:
- Nodes:
GeographicPointintersections - Edges: directed, weighted road segments
🔍 Demo: Visualizing loaded intersections on the map
BFS is used for unweighted shortest path discovery.
- Time Complexity:
O(V + E) - Space Complexity:
O(V) - Optimal: Yes, for unweighted graphs
- Use Case: Scenarios where edge weights are irrelevant (e.g., basic pathfinding, board games)
🧭 Demo: BFS explores shortest unweighted path
Dijkstra computes shortest paths on weighted graphs with non-negative edge costs.
- Time Complexity:
O((V + E) log V)with priority queue - Space Complexity:
O(V) - Optimal: Yes
- Use Case: GPS routing where travel distances or times differ across roads
🛣️ Demo: Dijkstra’s algorithm finds optimal weighted paths
A* uses heuristics to prioritize promising paths, reducing unnecessary exploration.
- Time Complexity:
O((V + E) log V)(average case) - Space Complexity:
O(V) - Optimal: Yes, with admissible heuristics (e.g., straight-line distance)
- Use Case: Real-time routing with performance constraints (e.g., robotics, games)
🧠 Demo: A efficiently finds optimal route using heuristics*
MapGraph.java– Graph structure and algorithm implementationsMapNode.java– Node representationMapEdge.java– Edge representation
Contributions are welcome! To contribute:
- Fork this repository
- Create a new branch:
git checkout -b feature/your-feature-name
- Commit and push your changes
- Open a pull request with a detailed description
- Course & Starter Code: UCSD MOOC Team
(Mia Minnes, Christine Alvarado, Leo Porter, Alec Brickner, Adam Setters) - Project Implementation: Jitendra Bhamare
Licensed under the MIT License. See the LICENSE file for full details.
For questions or issues, feel free to open an issue or contact via email:
📧 jitendra@email.com