1

So, I have been doing research about solving the Game Strategy problem of ICPC 2014 (page 7).

This consist in a board game with n boxes, each box have a unique set of paths that goes to another box on the board (can have a path that goes to itself). I think a graph would be a good representation of the game, more specific a directed graph

graphic case representation whit n = 2

I found 2 possible algorithms that should solve the problem:

1.- A YouTube video where it says that i should use the Breadth-first search

2.- Blog commenting the solution of some of the problems of that ICPC year. The author says that DP (dynamic programming) can be used. In Wikipedia's page is explained an algorithm called Dijkstra's algorithm which is used for "the shortest path problem" as the page says.

Is one of these algorithms an better solution for the problem? does one of those have better performance or something like that?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
S.Pardo
  • 13
  • 4
  • "better" how? faster? smallest code footprint? smallest RAM usage? most suitable for X platform scenario? StackOverflow is not geared toward providing opinions about programming; StackOverflow is geared toward specific programming problems; e.g., "I tried to benchmark my program comparing some shortest-path path algorithms, but received output of X when the documents suggest I should expect Y" ... that sort of thing – landru27 Nov 12 '18 at 03:34

1 Answers1

1

You use Breadth-first search (shortyly BFS) when the graph's edges are without weight (as your case) and Dijkstra's algorithm for weighted graph.

As a side note, remember that Dijkstra doesn't work when you have edges with negative values.

Thinking of complexity, this question might be in your interest: Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?

Emadpres
  • 3,466
  • 2
  • 29
  • 44