Find Cheapest Delivery Route
This problem is based on a delivery app kind of situation. You have several locations connected by roads, and each road has a travel cost. The job is to figure out the cheapest total cost to get from the starting point to the destination.
The tricky part is that the direct road is not always the best one. Sometimes a route with more stops ends up cheaper overall, so you need to compare total cost, not just the next move.
For example, if you can go from 1 to 2 with cost 5, from 1 to 3 with cost 2, and from 3 to 2 with cost 1, then reaching 2 through 3 costs only 3. That is cheaper than taking the direct road.
So the task is to find the minimum travel cost from the start location to the target location. If there is no route that reaches the target, return -1.
Example Input & Output
The cheapest route is 1 -> 3 -> 2 -> 4 with total cost 5.
The cheapest path is 1 -> 3 -> 2 -> 5 with total cost 6.
There is no route that reaches location 3.
Algorithm Flow
Solution Approach
A good method for this problem is to keep track of the best cost you know so far for each location, and keep improving those costs as you discover better routes.
The reason this works well is that you do not need to guess the full route all at once. You can build the answer piece by piece by always expanding the location that currently has the smallest known total cost.
We start by storing a very large value for every location, because at the beginning we do not know any route yet. Then we set the starting location cost to 0, since it costs nothing to begin there.
The update rule looks like this:
If new_cost is smaller than the cost we had saved for the next location, we replace the old value. That means we found a cheaper way to get there.
The main loop keeps choosing the unvisited location with the smallest known cost. From there, it checks all outgoing roads and updates the neighboring locations when a cheaper route appears.
If we eventually reach the target location, the saved value for that location is the cheapest possible total cost. If the target still has the large default value after processing, then it was never reachable, so the answer is -1.
So the full idea is: start from the source, keep the cheapest known cost for every location, and repeatedly improve those costs until the destination is settled or no reachable locations remain.
Best Answers
program cheapest_delivery_route
dictionary
n, i, current, node, start_loc, target_loc, best_cost, new_cost, answer, done, m: integer
roads: array[1..500] of integer
dist: array[1..100] of integer
visited: array[1..100] of boolean
algorithm
input(n, roads, start_loc, target_loc)
m <- roads.length
for i <- 1 to n do
dist[i] <- 1000000000
visited[i] <- false
endfor
dist[start_loc] <- 0
done <- false
while done = false do
current <- -1
best_cost <- 1000000000
for node <- 1 to n do
if visited[node] = false AND dist[node] < best_cost then
best_cost <- dist[node]
current <- node
endif
endfor
if current = -1 then
done <- true
else
if current = target_loc then
done <- true
else
visited[current] <- true
for i <- 0 to m - 1 do
if roads[i][0] = current then
new_cost <- dist[current] + roads[i][2]
if new_cost < dist[roads[i][1]] then dist[roads[i][1]] <- new_cost endif
endif
endfor
endif
endif
endwhile
if dist[target_loc] = 1000000000 then answer <- -1 else answer <- dist[target_loc] endif
output(answer)
endprogramComments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this Challenge.