Shortest Paths & Seam Carving

Problem & Motivation:

Given a weighted directed graph, compute the shortest path from a source to all reachable vertices. Then use those techniques to find a minimum-energy vertical seam in an image.

Data & Approach:

• Represented graphs using the adjacency-list structure provided in the project.
• Implemented Dijkstra’s algorithm by repeatedly relaxing edges until all shortest paths were finalized.
• Implemented the shortest-path algorithm for directed acyclic graphs using a topological ordering and a single pass of edge relaxations.
• Applied dynamic programming to the seam-carving task by treating each pixel as a vertex with an energy value and computing the minimum-energy path from top to bottom.
• Compared runtimes of the different shortest-path approaches as graphs and images grew in size.

Results:

• Both graph-based algorithms produced correct shortest paths under the project’s test cases.
• The dynamic-programming approach for seam carving was significantly faster because the underlying graph is always a directed acyclic graph.

Limitations:

Focused only on single-seam removal and the algorithms required in the specification; did not extend to removing multiple seams or modifying the energy function.