Hello! In this article, we will discuss the “Minimum Cost Finding” algorithm problem based on the pathfinding problem. Coding tests are one of the essential elements to prepare for employment in IT companies. To develop problem-solving strategies, understand algorithms, and improve implementation skills, we will solve the problem step by step through this article.
Problem Description
The problem of finding the minimum cost is about finding the minimum cost from a starting point to a destination in a given graph.
Let’s take the following graph as an example.
1 --> 2 (cost: 4)
1 --> 3 (cost: 2)
2 --> 3 (cost: 1)
2 --> 4 (cost: 5)
3 --> 4 (cost: 8)
Find the minimum cost to get from node 1 to node 4 in the graph above.
Input Format
- The first line contains the number of nodes N and the number of edges M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10^4).
- From the second line onwards, M lines provide the information of each edge in the format “u v c” (u, v are node numbers, c is the cost).
- The last line contains the starting node and the destination node.
Output Format
Print the minimum cost to get from the starting node to the target node. If there is no path, print -1.
Problem Approach
This problem is a typical problem of finding the shortest path in a graph, and we will use Dijkstra’s algorithm. Dijkstra’s algorithm is very efficient for finding the shortest path in weighted graphs. We will implement the algorithm through the following steps.
- Input: Enter node and edge information.
- Graph Structuring: Represent the graph as an adjacency list based on the input edge information.
- Priority Queue Initialization: Set up a priority queue to manage the costs of adjacent nodes from the current node.
- Perform Dijkstra’s Algorithm: Extract the node with the lowest cost from the queue and update the costs to the adjacent nodes.
- Output the Result: Verify if the destination is reachable and output the minimum cost.
Code Implementation
import sys
import heapq
def dijkstra(start, goal, graph, n):
# Initialize cost table
INF = float('inf')
distance = [INF] * (n + 1)
distance[start] = 0
queue = []
heapq.heappush(queue, (0, start)) # (cost, node)
while queue:
current_cost, current_node = heapq.heappop(queue)
# Ignore if the current cost is greater than the existing minimum cost
if current_cost > distance[current_node]:
continue
for neighbor, cost in graph[current_node]:
new_cost = current_cost + cost
# Update the cost of adjacent nodes
if new_cost < distance[neighbor]:
distance[neighbor] = new_cost
heapq.heappush(queue, (new_cost, neighbor))
return distance[goal] if distance[goal] != INF else -1
if __name__ == '__main__':
n, m = map(int, sys.stdin.readline().strip().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v, c = map(int, sys.stdin.readline().strip().split())
graph[u].append((v, c))
start, goal = map(int, sys.stdin.readline().strip().split())
result = dijkstra(start, goal, graph, n)
print(result)
Code Explanation
The above code implements Dijkstra's algorithm in Python. It takes the starting node, destination node, graph structure, and total number of nodes as input parameters.
- Cost Table Initialization: Initializes a list with infinity for the number of nodes. Sets the cost of the starting node to 0.
- Using a Priority Queue: Utilizes Python's heap feature, heapq, to process the node with the lowest cost.
- Updating Adjacent Nodes: Iterates through adjacent nodes to update them with the optimal cost.
Execution Example
Input 4 5 1 2 4 1 3 2 2 3 1 2 4 5 3 4 8 1 4 Output 6
This example shows that the minimum cost from node 1 to node 4 is 6.
Finding Minimum Cost in a Grid Graph
The above problem is a general graph, but there is also the problem of finding the minimum cost in a 2D grid. In the following sections, we will explain how to find the minimum cost using a 2D array.
Problem 2: Finding Minimum Cost in a Grid
In the given 2D array, you need to find the minimum cost to move from the starting point (0, 0) to the destination point (n-1, m-1). The value of each cell represents the cost of moving. You can only move up, down, left, or right.
Input Format
3 3 1 2 3 4 1 2 1 5 3
The given array is as follows:
1 2 3 4 1 2 1 5 3
Output Format
Print the minimum cost to get from the starting point to the target point.
Problem Approach
This problem can be solved using dynamic programming. The minimum cost is calculated at each cell by updating the minimum cost from the previously reachable cells.
Code Implementation
def min_cost_in_grid(grid):
n = len(grid)
m = len(grid[0])
dp = [[0] * m for _ in range(n)]
dp[0][0] = grid[0][0]
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
continue
up = dp[i-1][j] if i > 0 else float('inf')
left = dp[i][j-1] if j > 0 else float('inf')
dp[i][j] = grid[i][j] + min(up, left)
return dp[n-1][m-1]
if __name__ == '__main__':
grid = [
[1, 2, 3],
[4, 1, 2],
[1, 5, 3]
]
result = min_cost_in_grid(grid)
print(result)
Code Explanation
The above code shows how to find the minimum cost in a 2D array. It stores the minimum cost for each cell in a dp array and sets the current cell's minimum cost by comparing costs coming from the left or above.
Execution Example
Output 8
This example shows that the minimum cost to go from (0, 0) to (2, 2) is 8.
Conclusion
In this article, we explored various approaches and algorithms to solve the minimum cost problem. I hope the insights from the graph problem using Dijkstra's algorithm and the grid problem using dynamic programming will help you prepare for coding tests. Challenge yourself with various problems to enhance your problem-solving skills!
If you have any questions or additional inquiries during the process, please leave a comment. Thank you!