Monday, June 7, 2010

Update to Assignment 1

I kept thinking about the assignment and found the negative weight search problem so interesting that I went back and spent another hour or so on it. I now have a full solution to the standard and both bonus assignments that includes solutions for graphs with negative weights.

Main fixes

  1. Fixed an error in my implementation of the Bellman-Ford algorithm. I misread the bounds of the inner loop: I thought it looped through all the edges in the current node, but rather, it loops through all the edges of the entire graph. I was able to simplify the code considerably once I realized my error.
  2. I also realized that for the bonus questions, any negative weight node can be used in a cycle, and this will break the Bellman-Ford algorithm. For example:
    1. Input is: 
    2. "B1"
    3. "3 3 1,1 2,3"
    4. "1 -10 2"
    5. "5 2 -1"
    6. "2 1 3"
    7. There is a cycle between nodes (1,2), and (2, 3). The Bellman-Ford algorithm cannot handle this case.
  3. To solve this challenge, I implemented a brute force exhaustive search that tries searching all nodes to all nodes recursively. This is not elegant but solves the problem quickly enough for small data sets. My solution is more of a proof of concept than anything and could use some heavy optimization. The best way to do this would be to profile the code, and see where the hotspots are.
  4. Fixed a potential array index out of bounds error when inputting start and end nodes.
The code is available here.

No comments: