Graph Algorithms

Rotten Oranges Problem

Introduction:

The Rotten Oranges problem involves a grid where each cell is either empty (0), contains a fresh orange (1), or a rotten orange (2). The goal is to determine the minimum time required to rot all fresh oranges by simulating the spread of rot from rotten oranges to adjacent fresh ones using a grid-based approach.

Approach:

Graph Representation: The grid is treated as a graph with each cell as a node and edges between adjacent cells.

BFS (Breadth-First Search): BFS is used to simulate the minute-by-minute spread of rot, starting from all initial rotten oranges and spreading to fresh ones.

Applications and Learning Points:

This problem demonstrates practical applications of BFS in grid traversal and problem modeling using algorithms.

⁠

Dijkstra’s Algorithm

Introduction:

Dijkstra’s Algorithm finds the shortest path from a single source node to all other nodes in a graph with non-negative weights, commonly used in network routing and navigation.

Steps:

Initialization: Set the starting node’s distance to 0 and others to infinity, using a priority queue to process nodes.

Processing Nodes: Update distances to neighboring nodes if a shorter path is found.

Finalizing Paths: Continue until all nodes are processed.

Complexity:

Time Complexity: O((V + E) log V) with a min-heap.

Space Complexity: O(V).

Limitations:

Dijkstra's Algorithm doesn't work with graphs containing negative weight edges.

⁠

Bellman-Ford Algorithm

Introduction:

The Bellman-Ford Algorithm handles graphs with negative weight edges and can detect negative weight cycles, offering more versatility than Dijkstra’s Algorithm.

Steps:

Initialization: Set the starting node’s distance to 0 and others to infinity.

Relaxation: Iterate over all edges multiple times, updating shortest paths.

Negative Cycle Detection: Check for any further distance updates to detect negative cycles.

Complexity:

Time Complexity: O(V * E).

Space Complexity: O(V).

Applications:

Useful in scenarios involving negative weights, such as financial models or network routing.

⁠

Floyd-Warshall Algorithm

Introduction:

Floyd-Warshall finds the shortest paths between all pairs of nodes in a graph, particularly effective in dense graphs.

Steps:

Initialization: Create a distance matrix for all pairs of nodes.

Using Intermediate Nodes: Check if any node can serve as an intermediate point to shorten paths.

Updating Distances: Update the distance matrix accordingly.

Complexity:

Time Complexity: O(n³).

Space Complexity: O(n²).

Applications:

Ideal for solving problems involving shortest paths between all pairs, such as in routing and network analysis.

For more detailed information, refer to the Notion link:

Graph Algorithm⁠

⁠

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.