0

I have rectangle graph represented by two-dimensional table (I cannot change the form of graph representing) like that :

bool graph[n][m]; //where n and m are dimensions of rectangle

It looks generally like that :

enter image description here

My question is : What's best way in my case to represent distances between graph's vertexes ?

And : How can I use in that case BFS of Dijkstry alghoritm to find shortest path from graph[x0][y0] to graph[x1][y1] ?

I tried to search in internet for proper solution, but I saw only codes based on vectors, lists and struct(s).

IMPORTANT EDIT :

I'm sorry very well. My graph is rectangle only at the beginning. Then it is getting some changes (in distances between vertexes) and changing is form to something different. Please get attetion on that.

Community
  • 1
  • 1
TN888
  • 7,659
  • 9
  • 48
  • 84
  • What do the booleans in that array represent? – John Kugelman Dec 30 '13 at 21:49
  • @JohnKugelman That is less important. Is that field "empty" or "full" – TN888 Dec 30 '13 at 21:51
  • By "distances", do you mean the number of edges? So the distance from [2][1] to [5][0] is 4? – Beta Dec 30 '13 at 21:51
  • @Beta no ! I meant distances got from user's input. – TN888 Dec 30 '13 at 21:55
  • To *represent* the distance, wouldn't you just use an int? (Or maybe two, if you need to represent horizontal and vertical distance separately.) If the bool values don't represent anything germane to the distance, then isn't the distance simply x1–x0, y1–y0? A breadth-first search wouldn't gain you anything. – Rob Kennedy Dec 30 '13 at 21:58
  • **I'm sorry very well. My graph is rectangle only at the beginning. Then it is getting some changes (in distances between vertexes) and changing is form to something different. Please get attetion on that.** – TN888 Dec 30 '13 at 22:03
  • Are the edges directed? – Beta Dec 30 '13 at 22:08
  • @Beta No, there're not. – TN888 Dec 30 '13 at 22:09

2 Answers2

2

Assuming your "graph" is indeed a map where you can stay and move only on true cells when they're adjacent then a simple algorithm is based on the flood-filling idea:

  • create an "active list" of points where you place just (x0, y0)
  • at each "step" you consider all neighbors of a point in the active list and if the neighbor can be walked on and wasn't visited yet then you link it to the cell you're coming from and mark it as as visited. All the points you link are also added to a "new active list" collection.
  • a the end of the step you start again with the new active list instead of the previous one
  • the algorithm ends when either 1. the list is empty, 2. you find (x1, y1). In the last case there is a path and the shortest one can be reconstructed by following the links you saved.
6502
  • 112,025
  • 15
  • 165
  • 265
  • Yes I can stay only at `true` cells but I can "jump" over the `false` cell if the next cell is `true` – TN888 Dec 30 '13 at 22:28
1

How about this:

unsigned int horizontalEdges[n][m-1];
unsigned int verticalEdges[n-1][m];

And what part of Dijkstra's algorithm is proving difficult?

Beta
  • 96,650
  • 16
  • 149
  • 150