So I have a problem, and it's an assignment from school.
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).
