1
$\begingroup$

So I have a problem, and it's an assignment from school.
Graph
This is a figure made out of matchsticks. The goal is to find the optimal location to light up the figure so that it burns in minimal time. You can only light it up at integer positions (C,B) but not A. Different matchsticks may have different burn times.

My approach to this problem:

  • Iterate through every possible "light up" point
  • For every "light up" point, light up the figure and wait it to burn completely
  • Store the time it took to burn
  • Once iteration is complete, find the lowest time and there's your answer

The problems with my approach

  • Burning each figure will take a while since it's done realtime. It's also possible to do it faster then realtime, but I still don't think it's a viable solution.

Problems with center of a weighted graph:

  • What if we come up with A as the center?

Solution:

  • Just pick the next potential center and check if it's a valid "light up" point.

So I'm looking for a graph algorithm that can calculate the center on a weighted graph. I've never dealt with graph algorithms before, so that's why I'm asking here. I'm also just asking for you to point me in the right direction, and not write the code for me (although I guess some pseudo code will come in handy).

$\endgroup$

1 Answer 1

1
$\begingroup$

Use the Floyd-Warshall algorithm to compute all-pairs shortest paths (i.e., compute the distance between each pair of nodes). Then it is easy to find the center of the graph by enumerating all possibilities for the center node. The running time will be $O(n^3)$.

$\endgroup$

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.