EECE 352

Problem Set # 12

Due: December 3 (Thursday)

Fall 1998

Problem: The standard Kevin Bacon game is old new. It is time for a new twist. How about finding the path using those movies that people have given a high rating?

Task(100%): The data file I gave you includes an "R:" field with readGraph() parses into the rating variable but never actually uses. Your mission is to change your working PS#11 program (if you did not get it to work you can use mine, in the class homepage) so that edges will have weights. Then use Dijkstra’s algorithm to calculate the shortest path.

  1. Since the ratings are out of then, and Dijkstra’s algorithm is for calculating the shortest path, you will need to set the weights to be equal to 11-rating.
  2. The algorithm in Figure 9.32 in the book is wrong, line 12 should say t[w].known (not t[v].known).
  3. You will need to rewrite all of calculateShortestPaths, as well as making small changes in various other parts of the program.
  4. You do not need to use a priority queue to implement "Smallest Unknown Distance Vertex". It is OK to do it in O(|V|) time.
  5. Remember: infinity is bigger than any number, and –1 is not.

Using the "11 – rating" weights and the same main.cpp as before, I found:

We added 247 movies, 9384 actors, and 651070 edges.

Calculating distances from Bacon, Kevin

===Finding path to Pfeiffer, Michelle

Pfeiffer, Michelle was in Dangerous Liaisons (1988) with Malkovich, John

Malkovich, John was in In the Line of Fire (1993) with Senzy, Arthur

Senzy, Arthur was in Few Good Men, A (1992) with Bacon, Kevin

===Finding path to Smith, Will

Smith, Will was in Men in Black (1997) with Rankin, Steve

Rankin, Steve was in Apollo 13 (1995) with Bacon, Kevin

===Finding path to Banderas, Antonio

Banderas, Antonio was in Interview with the Vampire (1994) with Cruise, Tom

Cruise, Tom was in Few Good Men, A (1992) with Bacon, Kevin

===Finding path to Goldblum, Jeff

Goldblum, Jeff was in Player, The (1992) with D'Onofrio, Vincent

D'Onofrio, Vincent was in JFK (1991) with Bacon, Kevin

===Finding path to Madonna

Madonna was in Evita (1996) with Pryce, Jonathan

Pryce, Jonathan was in Brazil (1985) with De Niro, Robert

De Niro, Robert was in Sleepers (1996) with Bacon, Kevin

===Finding path to Hopkins, Anthony

Hopkins, Anthony was in Silence of the Lambs, The (1991) with Corman, Roger

Corman, Roger was in Apollo 13 (1995) with Bacon, Kevin

Press any key to continue