I have been tasked with creating a program that reads from an input file a numbe

Question

I have been tasked with creating a program that reads from an input file a number of intersections (Vertices) and streets (edges) to form an undirected weighted graph. The program is to do the following:

The program should search the provided graph to find jogging paths that meet the following requirements:

1) The path must start and end at the same intersection (i.e. vertex) indicated by the user-specified startingIntersection.

2) The path should not revisit any intersections. In other words, no vertex should appear twice within the path (as in a singular path).

3) The path should have a total distance within 1 mile of the user-specified distance goal.

The intersections and streets are read from a file. I have successfully parsed the data from the file and created the graph.

What I want to do now is put this into a search algorithm and find the paths which meet a user defined distance (within +/- 1 mile). For example, the user will designate how far they want to jog, what intersection (vertex) they want to start at, and then the algorithm should find what paths meet the user's criteria.

Again, this is a weighted undirected graph. Each edge has a weight associated with it, which is considered the distance.

There can be multiple paths that meet the criteria.

For example:

User says start at vertex #1 and wants to go 10 miles. The algorithm will search through all of the vertices and adjacent edges to find a route which matches (within +/- 1 mile) the users desired distance.

So say it finds the following paths:

Vertex 1 -> Vertex 4 -> Vertex 2 -> Vertex 1 = 9 miles.

Vertex 1 -> Vertex 3 -> Vertex 5 -> Vertex 1 = 10 Miles.

Vertex 1 -> Vertex 3 -> Vertex 6 -> Vertex 1 = 11 Miles.

All of which would be okay, and displayed to the user.

Thus far I have been considering some kind of Depth First Search:

Graph g = My graph that does not use adjacency lists/matrixes. It contains a vector<Vertex> VertexList, with each Vertex having it's own vector<Edge> EdgeList.

startingIntersection = The user defined intersection (vertex) they want to start at.

distanceInMiles = The distance the user wants to travel.

vector<Vertex> Graph::FindPaths(Graph &g, int startingIntersection, float distanceInMiles)

-- Which returns a vector<Vertex path list which matches the user's criteria.

However, I am having a hard time implementing this. If anyone could provide somepseudo-code or some ideas on how to approach this, I would be grateful!

Explanation / Answer

This seems like a fundamentally algorithmic problem, rather than an implementation-specific one, so I have provided detailed, high-level pseudocode for the algorithm rather than actual code. Also, I don't know C++. Let me know if any of the syntax/logic is unclear, and I can clarify some more. It essentially does a DFS, but doesn't stop when it finds the value: it continues searching, and reports all paths to the value (which meet the given distance criterion). // Input: Graph G, Vertex start, Integer targetDistance // Output: Set paths FindPaths ( G, start, targetDistance ): create an empty set, paths create an empty set, visited create an empty stack, currentPath // Iterative Exhaustive DFS push start on currentPath while ( currentPath is not empty ): current = pop ( currentPath ) if ( current equals start ): copy currentPath to a list, L (reversed order doesn't matter) find its weight, w if ( w+1 >= targetDistance AND w-1

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.