# Homework: Brute force graph search

Page 1 of 1

## 3 Replies - 1490 Views - Last Post: 22 April 2014 - 11:24 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=345351&amp;s=8ca565cb9eec58d114c2e1dac45c9286&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Mordoc

Reputation: 0
• Posts: 2
• Joined: 21-April 14

# Homework: Brute force graph search

Posted 21 April 2014 - 05:13 PM

As a homework assignment, I have to do a brute force graph search, and use those results to find the shortest route between two nodes in a weighted graph.
In this function I'm trying to recursively find all paths from the children of a node to the goal which are shorter than the maxDistance, and build up a complete list of routes.

```def validPaths(graph, start, end, maxTotalDist, path = []):
""" start and end are nodes in the graph
maxTotalDistance is an int which should be the limit of how far you should travel on a weighted graph"""
path = path + [start]
if start == end:
return path
allChildrenPaths = []
if getTotalLength(path, graph) < maxTotalDist: # check to make sure the path is shorter than MaxTotalDistance
for child in graph.childrenOf(start):
if child not in path: # so it doesn't contain loops, only include new nodes.
newPaths = validPaths(graph, child, end, maxTotalDist, path) #find all valid paths for the child
if newPaths != None:
allChildrenPaths = allChildrenPaths + newPaths #generates a list of all the paths from all the children
validPathsList = []
for route in allChildrenPaths: #take all the children's paths, and append the parent node
validPathsList.append([start] + route)
return validPathsList
```

Here is what I have so far, but it doesn't work properly. It seems to give me a short route, and then a bunch of empty lists until it gets to an error when trying to append a node to a list, though, I don't understand where this is coming from. Please help me find the error in my code. At first I would appreciate hints and general nudges in the right direction so I can understand what I'm doing wrong and learn from it.

Is This A Good Question/Topic? 0

## Replies To: Homework: Brute force graph search

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11798
• Posts: 44,322
• Joined: 27-December 08

## Re: Homework: Brute force graph search

Posted 21 April 2014 - 07:20 PM

Are you sure "brute force" is the right term? The same thing can be accomplished with a greedy breadth-first search. It's called Dijkstra's algorithm.

### #3 Mordoc

Reputation: 0
• Posts: 2
• Joined: 21-April 14

## Re: Homework: Brute force graph search

Posted 21 April 2014 - 08:22 PM

macosxnerd101, on 21 April 2014 - 07:20 PM, said:

Are you sure "brute force" is the right term? The same thing can be accomplished with a greedy breadth-first search. It's called Dijkstra's algorithm.

I had looked at that algorithm when trying to figure out the answer, but I didn't think it quite fit. The instructions were to list every path (hence brute force) that could go from the start node to the finish node which is shorter than the maximum distance, then see which one was the shortest. This is the helper function I wrote to list all of the paths from node A to node B. It is not supposed to be an optimized search, that is another problem in the same problem set, and I can wrap my head around that function better. It's also supposed to be a depth first search instead of a breadth first search, though I might have messed that part up.

### #4 Nallo

• D.I.C Regular

Reputation: 165
• Posts: 258
• Joined: 19-July 09

## Re: Homework: Brute force graph search

Posted 22 April 2014 - 11:24 AM

I have really trouble understanding what your code is supposed to do.

Sometimes it's better to start again from scratch.
As you told us now your search is supposed to be based on a DFS algorithm.
It might be a good idea to start with a normal DFS and look if you can change it
in a way to solve your problem.

another hint, but please try without:
Spoiler