Dijkstra, Bellman Ford application on map in double arrays

Question

I have on input such a map:

int map_w = 40;
int map_h = 20;
char map[20][40] = {
    {'c', 'c', 'c', 'c', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'c', 'c', 'n', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'n', 'n'},
    {'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'n', 'n', 'h', 'h', 'n'},
    {'c', 'c', 'c', 'c', 'n', 'c', 'n', 'n', 'c', 'c', 'h', 'n', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'n'},
    {'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'n', 'c', 'n', 'n', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'h', 'n'},
    {'h', 'h', 'h', 'h', 'c', 'c', 'c', 'n', 'c', 'c', 'h', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'n', 'c', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'h', 'h', 'n', 'h', 'n', 'h', 'n'},
    {'n', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'h', 'n', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'h', 'h', 'h', 'p', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'n', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'h', 'h', 'h', 'h', 'n', 'h'},
    {'c', 'c', 'c', 'n', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'p', 'h', 'h', 'h'},
    {'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'h', 'h', 'c', 'n', 'n', 'n', 'c', 'c', 'c', 'd', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'h', 'c', 'h', 'h', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'h', 'h', 'h', 'n', 'h', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'n', 'c', 'n', 'c', 'n', 'c', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'n', 'c', 'h', 'h', 'n', 'h', 'n', 'h'},
    {'n', 'c', 'c', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'n', 'c', 'h', 'h', 'h'},
    {'n', 'c', 'n', 'n', 'c', 'n', 'c', 'n', 'c', 'p', 'h', 'h', 'h', 'n', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'c', 'n', 'c', 'h', 'h', 'h'},
    {'n', 'n', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'h', 'h', 'c', 'h', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'n', 'n', 'h', 'h', 'n'},
    {'n', 'n', 'n', 'c', 'c', 'n', 'n', 'n', 'c', 'h', 'h', 'c', 'h', 'n', 'c', 'h', 'n', 'n', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'n', 'h', 'h', 'n'},
    {'n', 'n', 'n', 'n', 'n', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'n', 'n', 'c'},
    {'n', 'n', 'c', 'c', 'n', 'c', 'n', 'n', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'c', 'n'},
    {'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'c', 'n', 'c', 'c', 'n', 'n', 'n', 'n', 'n'}
};

here's the image of the map that how it looks like:

the chars in array correspond with each square, that means, gray is h and this is a stone this way i cant go. brown is normal path(c) which length is 1 green is forest(n) which length is 2

then there's d as dragon and p as princesses, i have to first find the shortest way to dragon and then to princesses and return the the exact shortest path..

So my question no.1 is, is there some way to put this input to some modified Dijkstra, or Bellman-Ford, or some different algorithm? Or i have to first make for every square a connection, that from square 1,2 i can go to 1,1 and the length is 2, and to 2,2 and length is 2, or i can simply somehow run the algorithms through the double array??

question no.2 Which algorithm do you suggest to use? I thought of Bellman Ford, although i have no negative squares, i need to return the exact path and this is very easy thanks to array pi, which is maintained in Bellman Ford, but I'm opened for any suggestions, as I'm just getting into theory of graphs.

Answer 1

Well, both Bellman-Ford and Dijkstra algorithm are overkill in here, since the edges all have a weight of 1.
Note that you can create an auxilary vertex for the cases of weight=2, so instead having edges of weights 1,2 - you will have more vertices and edges, but all of wight 1, basically this is done by replacing edges in the form (u,v,2) to: (u,u',1) and (u',v,1) - for every edge with weight 2.
Note that at worst case it will give you 4|V| vertices and 4|E| edges, so it does not change the time complexity when it comes to big O notation.

In such graphs (unweighted/all edges weights the same), BFS is solving the problem efficiently and is much simpler to program than both BF and Dijkstra's algorithms.

An alternative is A* Algorithm with the manhattan distances heuristic function, or a bi-directional search, which is usually faster than a normal BFS for large scales.

---

PS, note that you can create the graph 'on the fly', by creating a next:V->(2^V x R) function, that for a given vertex v, the result of next(v) will be all its connections and weights. By doing so, you actually create the parts of the graph you need dynamically, and not during some pre-processing,

Let's assume you have the following, and assuming the cost of 2 is if you move to a forest (and not from a forest).

     a  b
     ____
1:   c  h
2:   n  c

In here, you have the edges (in the original graph):

((1,a),(2,a),2), ((2,a),(1,a),1), ((2,a),(2,b),1), ((2,b),(2,a),2)

By applying the modification I suggested you get: 6 edges instead of 4, and the idea is you get the edges ((1,a),(1_2,a_a),1) ((1_2,a_a),(2,a),1) instead of ((1,a),(2,a),2), and similarly for ((2,b),(2,a),2).

Now, in here, your next() function will be:

next(1,a) = [((1_2,a_a),1)]
next(1_2,a_a) = [(2,a),1)] //dummy nodes also need an output...
next(2,a) = [((1,a),1), ((2_2,a_b),1] //two nodes in here, because you can move to 2 nodes.
next(2_2,a_b) = [((2,b),1)]
next(2,b) = [((2,a),1)]

---

Note, since the problem seems to be of small scale, and by your own words, you are a beginner - I think applying BFS will be the best solution for your problem. Once you are done with it, you will be able to improve to a more efficient algorithm - but IMO, you should start with the simplest one, which is BFS.

Answer 2

If you were to represent the map as a graph explicitly, you'd have to identify the children of every node. So you could fill that explicit representation programmatically: every node (i>0,j) connects to (i-1,j), (i,j>0) connects to (i,j), (i

Answer 3

I suggest you give a close look at A*.

It is an easy and yet efficient way of finding paths, especially in 2D grids.