Battery-constrained shortest path using greedy selection (Dijkstra's) and a dynamic programming battery state table. Plans real EV trips across a 10-city road network, inserting recharge stops only when the next road segment cannot be completed.
Group members: Nabonita Das, Ali Hamza, Akash Patel · CIS 505
10
Cities in network
11
Road segments
1,120 mi
Longest feasible trip
0.05 ms
Execution time
Battery capacity
500 miles
Starting charge
50% = 250 mi
Total distance
1,120 miles
Recharge stops
3 (Ohio St, TN, GA)
Best route:
Battery state table (DP output):
| Step | From | To | Distance (mi) | Battery Before (mi) | Battery After (mi) | Recharged? | Total Charges |
|---|---|---|---|---|---|---|---|
| 1 | UM-Dearborn | U-M Ann Arbor | 35 | 250 | 215 | No | 0 |
| 2 | U-M Ann Arbor | Ohio State | 185 | 215 | 30 | No | 0 |
| 3 | Ohio State | Kentucky | 190 | 500 | 310 | Yes | 1 |
| 4 | Kentucky | Tennessee | 170 | 310 | 140 | No | 1 |
| 5 | Tennessee | Georgia | 230 | 500 | 270 | Yes | 2 |
| 6 | Georgia | Univ of Florida | 310 | 500 | 190 | Yes | 3 |
Spikes show recharge events at Ohio State, Tennessee, and Georgia. The red dashed line marks the 310-mile minimum needed for the longest road segment.