Introduction
Shortest Path algorithm is about finding the shortest
route from source to destination. In vehicle driver perspective, the route
model should incorporate gas cost and vehicle oil tank. Assuming every gas
stations price is different.
This scenario is to find the cheapest route from source to
destination.
At each gas station we may refill some amount of gas to extend
the vehicle mileage by a certain distance. Presume gas prices vary between
gas stations in different areas, the cost depends on where we purchase gas
from.
Contemplate
This is a computing intensive derivation, because it is using
try-and-compare / brute-force checking method. Lists out and computes all
the possible gas re-filling amount at each gas stations and choose the
cheapest total cost.
·
A vehicle with a given oil tank
capacity, it can only travel a distance on a full tank of gas. We can
derive the vehicle maximum travel distance by multiplying gas tank size
against the mileage per gas unit of the vehicle.
·
There are no correlations between
node-to-node distance and each Gas Station gas prices. Also, there are no
correlations between each Gas Station gas prices.
·
Shortest route may not be the
cheapest route. Although the shorter the total travel distance the cheaper
the total travelling petrol cost tend to be, but not always true.
Therefore, we cannot just deploy the Shortest Path algorithm.
·
Unlike total traveling distance, we
can sum-up all node-to-node distance. There are no stacking effects in gas
prices.
Assume:
·
Assume vehicle’s mileage per gas unit
is a constant value
·
Assume we start with some given
amount of gas in the gas tank.
·
Assume source node / starting node is
not a gas station
The Gas Stations problem can split into two portions, first
portion list-out all the possible non-repetitive paths from source node to
destination node; second portion is to derive the total cheapest gas
refilling combinations by trial-and-error method for each paths; and
finally get the cheapest total refilled gas amount among all the possible
paths.
List-out all
the possible paths from source node to destination node in a graph
This derivation
will list-out all the possible paths from source node to destination node
in a graph. All possible paths are saved in Lists format.
The derivation
method is to save the first edge in the node to the current path (List) and
the rest of the edges into the subsequence newly duplicated paths (List),
provided the node’ edges are found to be not re-occurring in the current path
(List). Repeat again from the last node of the list until it reaches the
destination node, a node that doesn’t have any outgoing edges or a dead-end
node.
A path that has
dead-end node means that the current path will not reach to the destination
node, because the dead-end node is either having edges that are already
re-occur in the current path or don’t have any outgoing edges.
Proceed the path-listing
using the next path in the list.
c++
Console App Source Code
Below coding only list-out all the possible paths from source node to destination
node in a graph.
In ‘Graph_1_AllPaths.txt’, ‘Graph_2_AllPaths.txt’, ‘Graph_3_AllPaths.txt’ and ‘Graph_4_AllPaths.txt’, 1st value in the
pair is the next destiny node ID, 2nd value is the path weight
List_All_Possible_Paths1.cpp Graph_1_AllPaths.txt Graph_2_AllPaths.txt Graph_3_AllPaths.txt Graph_4_AllPaths.txt
Figure:
‘GasStation_1’
Figure: ‘GasStation_2’
Figure:
‘GasStation_3’
Figure:
‘GasStation_4’
Find the cheapest
gas-refilling combinations at each gas stations among all the possible
traveling paths
Find the cheapest gas-refilling combinations at each
gas stations for every possible traveling paths. Afterward, find the grand
cheapest gas cost among all the possible paths.
Here the graph will only add the sub-paths that
are reachable by vehicle. That’s mean node’s edge weight should not exceed
the vehicle maximum travel distance under full gas
tank (derived from multiplying gas tank size against the mileage per gas
unit of the vehicle). At source / starting node, graph only add those edges
reachable by vehicle, as vehicle started with some given amount of gas in
the gas tank.
c++ Console App
Source Code
1.
Gas price, vehicle gas consumption,
distance, gas refilled amount and vehicle gas tank in integer
Fill_or_NotFill_GasStation_Problem_17.cpp GasStation_1.txt GasStation_2.txt GasStation_3.txt GasStation_4.txt
In the ‘GasStation_2.txt’ graph data
file, first row is the starting gas amount in the gas tank at source or
starting node before traveling. Second row onward, first value is the
current Gas Station gas price; second values onward, are the paired values.
First in the pair is the next destiny Gas Station; second value in the pair
is the traveling distance.
2.
Gas price, vehicle gas consumption,
distance, initial gas and gas refilled amount at each gas
stations in
float. Except vehicle gas tank in rounded lower whole value for ease of
computations.
Fill_or_NotFill_GasStation_Problem_21_float.cpp GasStation_1.txt GasStation_2.txt GasStation_3.txt GasStation_4.txt
|