## Overview¶

In this project, you will implement a content-aware image resizing algorithm. You are only required to implement `DijkstraShortestPathFinder`

and `DijkstraSeamFinder`

.

### File Description¶

In this project, you will implement a) a graph algorithm, b) a graph representation of a non-graph problem, and c) optionally, a dynamic programming algorithm for seam carving.

`DijkstraShortestPathFinder`

finds the shortest path by using Dijkstraâ€™s Algorithm. Your task is to implement the Dijkstra’s Algorithm learned in class.`DijkstraSeamFinder`

finds the seam to remove by using a reduction of the shortest path problem. You’ll be able to resize an image by seam carving after completing`DijkstraSeamFinder`

!`DynamicProgrammingSeamFinder`

is an optimized way to find the seam to remove by using dynamic programming. This is**optional**and worth a minor amonunt of extra credit if completed.

### Note¶

- We recommend you to work on the
`DijkstraShortestPathFinder`

**before**moving to the`DijkstraSeamFinder`

and try implementing`DynamicProgrammingSeamFinder`

only if time permits. - Once you complete the
`DijkstraShortestPathFinder`

, you may run through some (hidden) tests via GradeScope to make sure that your`DijkstraShortestPathFinder`

works as intended!

### Objectives¶

By the end, you will be able to:

- Solve a real-world graph problem via reduction.
- Represent problem solutions as states in a graph.
- Apply graph augmentation as a strategy for solving a new class of graph problems

## Getting Started¶

Task

Grab your partner(s) and set off on a new journey together!

If you are working in a group, consider scheduling a time to go over the spec together and discuss how to collaborate on the project. If you are working with a new partner, follow the instructions from the Deques assignment to add your partner into your group and pull the assignment from the public skeleton.

## Subpages

- Background - Familiarize yourself with Seam Carving and the assignment.
- Shortest Path Finder - Implement Dijkstra’s Algorithm to find the shortest path.
- Seam Finding - Implement the logic behind seam carving using two different techniques.
- Dynamic Programming Implementation