CODEWITHSUNDEEP
c++arraysalgorithmmatrix
Alessandro Lorusso
Alessandro Lorusso

Reputation: 357

Modifying the Breadth First Search algorithm to remember the shortest route in a matrix

I'm trying to find the shortest path between two given cities using the breadth first search algorithm. I then want to be able to print out that path. I have a matrix of cities stored in a multidimensional array (array[8][8]). The matrix looks like this:

    #1    #2     #3       #4     #5    #6        #7   #8
#1   0    100    -1       10     -1    -1        -1   100
#2  100     0    -1       -1     10    10        -1    -1
#3  -1     -1     0     1000    100    -1      1000    -1
#4  50     -1   720       -1    -1     -1       -1     -1  
#5  -1     10   100       -1      0    -1       100    -1
#6  -1     10    -1       -1     -1     0        50  2000
#7  -1     -1  1000       -1    100    10         0    -1
#8  100    -1    -1       -1     -1  1000        -1     0

If the number is above 0 then it means there is a path between those two cities. For example city #2 has a path to city #1 because it has the number 100. I need to find the shortest route from a given source city to a destination city.

My question is, is it possible to modify the breadth first search algorithm to do this on a matrix, or should I be storing the data in another data structure?

Upvotes: 0

Views: 224

Answers (1)

user5886152
user5886152

Reputation:

You need to be working with a Node class that has properties for the current node you're looking at, and it's parent, rather than just the raw node. So as you locate all nodes connected to the current node, you create a new object for the child node, and set the parent property as your current node.

Then once you've found the shortest path, you iterate up through the parent properties until you get to the root (which has a null parent).

That's the simple explanation (did I say "node" enough times?)... hope it makes sense.

Upvotes: 1

Related Questions