The Shortest Path Algorithm

"This is some mighty good gin and tonic R2. Can you mix me another one?" - Luke Skywalker

I have to mention the flash movie that quote is from because it's really really funny. It's called 'Star Wars Gangsta Rap' and it has great animation. Anyway, I'm kinda sad to be back here because I'm gonna miss everyone I saw over the weekend. All good things have to end or they wouldn't be good though, and once it kicks in that I'm in Austin I'm sure everything will be back to normal. I'm already getting excited about CS again with the introduction of a new algorithm. Let's say you have a directed graph that represents airplane routes for some airline and you want to find the shortest path from one location to another. How can you do it so that it doesn't take all eternity? You have to use a priority queue that stores where you can go to from each point with its path length as the weight and you have two other arrays to store the predecessor for each location and the total distance for each element. You return that list of predecessors to trace the route, and the point of the total distnace array is so that if you find a shorter path later on you can override what you currently have. The popping from the queue pops the least distant elements first of course. Here's what it looks like to clarify a bit:

public static int[] shortestPath (int[][][] a, int v1, int v2) {
   final int[] p = new int[a.length]; //array of predecessors
   final int[] s = new int[a.length]; //array of distances
   final Queue q = new PriorityQueue(a.length);
   for (int i = 0; i < a.length; ++i) {
      p[i] = -1;
      s[i] = Integer.MAX_VALUE;}
   p[v1] = v1;
   s[v1] = 0;
   q.push(new int[]{v1, 0});
   while (!q.isEmpty()) {
      final int[] e = q.pop();
      final int v = e[0];
      if (v == v2)
         return p;
      for (int j = 0; j < a[v].length; ++j) {
         final int w = a[v][j][0];
         final int x = a[v][j][1];
         final int y = s[v] + x;
         if (y < s[w]) {
            p[w] = v;
            s[w] = y;
            q.push(new int[]{w, s[w]});}}}
   return null;}}

Of course that's not all the nerdy stuff I have to share with you all today. In a huge blow to one of Sony's larger money making products, they have been ordered to pay $90.7 million to a Immersion Corporation and halt all sales of Playstations for patent infringement of the controller vibration technology. Those executives must really be sweating it out now. Speaking of sweating executives, Grokster is going on the flame tomorrow to be tried in the U.S. Supreme Court for copyright infringing file sharing. I'm split on what I want the result to be because both sides sound so convincing (read the article and you'll see) and UMG claims that they'd develop more legal alternatives to sharing if they won. Another thing the government has been involved in recently is campaign finance reform, and it turns out that bloggers barely escaped regulation for political content! I suppose there's no way it would've gone through though given the extensionability of the 1st amendment. If Microsoft Word's grammar checker has ever screwed you over on a paper, this is the the article to read. A couple of professors suggest that despite M$'s claims, they're not doing enough to improve the utility. If you're a fan of Adobe Photoshop this article highlighting the new features in CS2 is a must-read because the next iteration sounds really tight. And lastly, if you've missed out on all Yahoo's recent moves you'll want to read this spectacular post with all that information as well as some analysis.

The movie news for today is pretty decent. I haven't mentioned Domino in a while, so for those who don't remember I'm really excited about it because not only is it directed by Tony Scott (True Romance) and written by the imaginative Richard Kelly (Donnie Darko), but it features Keira Knightly, Christopher Walken, and Lucy Liu to name a few of the big names. The trailer for that flick is finally out to go check it out. While I'm blabbering about exciting movies I should plug this feature at IGN revealing information about the female cast of Sin City, which does contain spoilers. Don't forget to catch the movie this Friday, and those of you with some cash to throw around should catch the premiere on Thursday. Onto other big news though, there are rumors floating around that Quentin Tarantino is planning to cast Arnold Schwartzenegger, Sylvester Stallone, and Bruce Willis for his WWII flick Inglorious Bastards, and supposedly Harvey Keitel and John Travolta as well. As I've said before though, only Adam Sandler and Michael Madsen are confirmed for now. Bond fans will likely be perturbed to hear that Orlando Bloom may be cast to play a younger Bond in a series of movies hilighting the secret agent's early career. I really don't think he can pull off the image. Kevin Smith, aka Silent Bob, has started an online diary that is kinda cool since it's a window in the mind of a known director and reveals that The Passion of the Clerks will be the first film under the Weinstein brothers' new production company. In comic movie news, there's now Sandman concept art floating around the Spider-man offices, but we're still clueless as to the villain. The main villain of X3 has all but been confirmed to be Dark Phoenix, but apparantly it's not the main story. No idea what that means yet, but stay tuned for more. And lastly, take a look at the official Curious George poster.

Just a few quick items left. In a surprising survey, it turns out that a vast number of people in the British sample gave away enough information for identity theft in exchange for movie tickets! That sample isn't too representative, but it's something to think about. If you're a fan of anecdotal evidence though, check out this article that suggests that PSP sales were weak last week. And lastly, embrace this Penny Arcade comic referring to God of War, which I mentioned recently:



Get ready for some Monday Madness:

1. ___________ is more fun to celebrate than any other holiday.
Christmas, because making sweets is fun.
2. The last vacation I took was to __________.
Canada with my parents; the destination wasn't my choice.
3. The next vacation I plan to take will be to ___________.
No idea, but hopefully London.
4. I'd really like to be more _________.
Sociable I suppose. It's hard to meet new people!
5. I can't remember the last time I __________.
Swam in a creek
6. The book I last read (or am currently reading) is ________.
Da Vinci Code
7. The last program I installed on my computer was ________.
Starcraft 8-)
8. When it comes to food, my weakness is _________.
Ice Cream!
9. I really look forward to spending time _________.
with my brother