0
\$\begingroup\$

grid contains weights and I need a max path sum from one column to another possible movement directions are (right, up & down only).

Can Djikstra or A* help ??

\$\endgroup\$
0
1
\$\begingroup\$

What is a graph?

A graph consists of 3 things.

  1. objects called "vertices" (singular "vertex"),
  2. connections between the objects called "edges", which are ordered pairs of the form (a,b) this means that "a is connected to b", it does not mean that b is connected to a.*
  3. weights or worths assigned to the edges. This is done by a function, w: connections -> numbers with w(x,y) being the weight of the edge from x to y

Dijikstra and A*

These algorithms take a graph and the assumption that w(x,y)>=0 for all x and y and return a shortest path (between some or all vertices of the graph)+

They will work provided you can satisfy the definitions above.


Footnotes:

* - so called "undirected" graphs are graphs where if the edge (a,b) exists then so does (b,a) and they require that w(a,b)=w(b,a)

+ - suppose that your weight is "time taken" and you have a portal that'll take you back in time to a location p, the "weight" of going to p might be the weight to the portal - the time difference. Suppose you can go from p back to the portal before you even leave through the portal. This is called a negtive weight cycle and totally buggers up the algorithm (see Floyd's algorithm) - even if it isn't a negative weight cycle it causes severe problems.

\$\endgroup\$
1
  • \$\begingroup\$ Sometimes weights must be either fractions or integers! There's an algorithm for finding argumenting paths in flow networks (that might be Floyd's... hmm, will check that) and it only works if you have non-irrational weights. Dijikstra and A* do not suffer from this of course. \$\endgroup\$ – Alec Teal Sep 26 '15 at 19:12
0
\$\begingroup\$

Of course.

Dijkstra's (of which A* is just a refinement) adds nodes to an open list. The usual grid implementation is to consider all adjacent nodes. You can simply change this to only consider nodes on the same column or the column to the right.

For termination, the usual algorithm is looking for a specific node or position. You can also change the algorithm to terminate on a specific set of nodes ie. a specific column.

Ultimately, this is no different than games that filter out nodes for different types of units (e.g. airborne vs terrestrial vs aquatic units pathing over a map in an RTS) or games that search for points near a target location (e.g. to get within 10 meters of a point a user clicked, rather than the exact node the user clicked).

\$\endgroup\$
2
  • \$\begingroup\$ Before (something) on this answer - I'm currently writing - was beaten to the post! \$\endgroup\$ – Alec Teal Sep 26 '15 at 18:39
  • \$\begingroup\$ what should be the condition in hueristic function to find MAX SUM path ........instead of min \$\endgroup\$ – rahul Sep 26 '15 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.