Introduction
Given a weighted graph, there are multiple paths
from origin to destination. Weighted graph can means travel time, distance
or etc from one node to another node.
Find all the ways
we can travel from origin to destination, within total travel weight limit.
This
multiple-paths-search method is more pragmatic than shortest path search
method, as it gives users multiple ways to choose to reach the destination.
Shortest path search method only provides 1 shortest path to the
destination.
Methods:
Create a new path for each edge
nodes. Duplicate current path to the new paths.
Multiple travel paths from node to the
one edge node is allowed in this program.
If the edge node is the origin /
starting node, ignore this edge node. Search the next edge node.
If the edge node already existing in
the current path, ignore this node to prevent infinity self-looping. Search
the next edge node. If all edge nodes exist in the current path, the
current path is a dead-end path (Boolean variable isDeadEndPath
= true). Search the next path.
Move-on to the next path search if no
valid edge node in current path.
If current path s total weight
exceeds user s weight limit, stop current path search. Move-on to the next
path search.
If the neighbouring node is the
destination, add the destination node to the path & stop current path
search. Move-on to the next path search.
Use List to construct graph map and
to save paths search outcomes, as List is size expandable. In the list of
paths outcomes, each path itself is also a list, together with totalWeight to become nodes inside the paths outcomes
list.
Visual c# Console App
In graph1.txt file,
1st line is the node 0; 2nd line is the node 1; and
so on. Each pair in the line is the neighbouring node ID and the weight,
separated by a space.
main_v0.cs
graph1.txt
graph2.txt
graph3.txt
Graph 1
Graph 2
Graph 3
Reference
Code challenges
website (no answer): https://www.geeksforgeeks.org/problems/number-of-ways-to-arrive-at-destination/1
|