Lab: Shortest Paths

Algorithms

There are 2 main Shortest Path algorithms we will consider.

1. Djikstra’s Algorithm
2. Bellman-Ford Algorithm

Note: For this class, break ties alphabetically and start with vertex A when you have a choice of vertices to add/connect.

Problem 1 Djikstra’s Algorithm:

Consider the following weighted, undirected graph:

1. What is the shortest path from A to H?
2. What about from A to G?
3. Find the shortest path from A to all other vertices using Dijkstra’s Algorithm. Show your work, include your steps, and verify your solution with the instructors.
4. Find the shortest path from E to all other vertices using Dijkstra’s Algorithm.
5. Are the trees in parts 4 and 5 the same? Why or why not?

Problem 2 (Bonus) Bellman-Ford Algorithm:

Repeat Problem 1 with the Bellman-Ford Algorithm.

Problem 3: Theory behind the algorithms

1. If the weights of the edges in a graph are unique, will you get the same tree regardless of starting position using Dijkstra’s Algorithm? Why or Why not?
2. Does Djikstra’s Algorithm work with negative weight edges as long as there is no negative weight cycle? Why or why not?
3. Does Djikstra’s Algorithm work with negative weight cycles? Why or why not?
4. Given a weighted graph, G, and starting position, A. If we increase or decrease the weights of G by the same value, b, will we get the same shortest paths from A to the other vertices? Why or Why not?
5. Given a weighted graph, G, and starting position, A. If we multiply the weights of G by the same value, c, will we get the same shortest paths from A to the other vertices? Why or Why not?

Problem 4 (Bonus) Bellman-Ford Algorithm:

Repeat Problem 3 with the Bellman-Ford Algorithm.

Problem 5 (Bonus)

Which algorithm do you prefer?