(no subject)

[phthalombrage]

This xkcd strip was included in the spec for my last 211 lab. Graph algorithms. Dijkstra. Bellman-Ford.

Now that I have a digraph class and priority queue written, I think Dijkstra's is running. But before I started Bellman-Ford, I had this lovely procrastinatory response to the above comic (The last panel is shite, but I didn't want to procrastinate too much :P):

Comments

[conqueror49worm.livejournal.com]

I love how divulgling the body language is when they're only stick figures.

[etotheipi.livejournal.com]

No alt text?!

[phthalombrage]

There is! But Firefox doesn't like to display it on my machine... maybe you also have that problem? Maybe my computer is propagating that problem? I always have to right-click and check image properties to see it.

[chrisamaphone]

i think you need to make it "title text" in order to show up on mouse hover.

[phthalombrage]

Shiny. I remember alt alone used to do that, but those were probably the before I knew better than to use IE.

[phthalombrage]

the days.

[sageofminerva]

I'd argue that graph algorithms make excellent pillow talk. Of course, I enjoy listening to people talk endlessly about that stuff so my opinion is probably biased.

[hillary-havok.livejournal.com]

What is the Bellman-Ford algorithm? I've seen that comic a few times and I've wanted to know what it was referring to.

I like the way you draw stick figures. =]

[phthalombrage]

Wikipedia will tell you, but I dunno if you'd glean much from its description. Basically, Bellman-Ford will get you the shortest path between all vertices in a graph. It builds a table, from which you can calculate the shortest distance from any starting place to any ending place, staying only on existing edges between vertices (like mapquesting/google maps-ing something). It takes a long time to run through the possibilities the way the Bellman-Ford solution is implemented, so it's not the optimal solution to this problem in normal cases like mapquest, but there are cases where Bellman-Ford should be applied. The "weight" of your edges can mean other things than just "distance", which is always a nonzero integer. Say, for example, you're a pizza guy, and to calculate the cost of a run, you add cost of gas for travel and subtract tips you get. When, like the pizza guy, you can have negative edge weights, Bellman-Ford is a viable solution, and certain other algorithms that run faster on nonzero edges will fail/break. There are built-in checks to make sure you don't get stuck in a negative cost cycle (looping in a series of houses that tips a lot so you keep raking in profits... unrealistic in real life, but a harder situation to diagnose in an algorithmic model). In short, graph algorithm, finds shortest path, not normally all that great, but there are times when it's awesome that it exists.