﻿==================================================
5. MULTISTAGE GRAPH (DYNAMIC PROGRAMMING)
==================================================

ALGORITHM:
1. Represent the graph using a cost matrix.
2. Initialize all costs to INF.
3. Set destination cost = 0.
4. Process vertices backwards from the last stage.
5. Check all outgoing edges of the current vertex.
6. Calculate the cost of every possible path.
7. Store the minimum cost and next vertex.
8. Follow next[] to display the optimal path.

RECURRENCE RELATION:
Cost(i) = min { C(i,j) + Cost(j) }

BASE CONDITION:
Cost(destination) = 0

RECURRENCE:
Uses iterative Dynamic Programming (backward approach).

TIME COMPLEXITY:
Best Case    : O(V^2)
Average Case : O(V^2)
Worst Case   : O(V^2)
Space        : O(V) auxiliary space