One of the common problems that appears in coding tests is the ‘Minimum Cost Path’ problem.
This problem requires minimizing costs while satisfying certain conditions,
and can be efficiently solved using various algorithms.
In this article, we will explore how to solve the minimum cost path problem using C# in detail.
Problem Description
In the given graph, each edge has a specific cost.
When tasked with finding the minimum cost path from a starting vertex to all other vertices,
we need to solve this efficiently.
Problem Definition
Let the number of vertices be N and the number of edges be M.
Suppose we are given a graph that satisfies the following conditions:
- N (1 <= N <= 1000): Number of vertices
- M (1 <= M <= 10000): Number of edges
- Costs are integers between 1 and 10000
Input: Information about the starting vertex and the costs between each vertex is provided.
Output: An array of the minimum cost paths from the starting vertex to all other vertices is returned.
Example
Input
5 7
1 2 2
1 3 3
2 3 1
2 4 5
3 4 1
3 5 5
4 5 2
1
Output
0 2 3 7 5
In the above example, starting from vertex 1,
it takes a cost of 2 to reach vertex 2, 3 to reach vertex 3, 7 to reach vertex 4, and 5 to reach vertex 5.
Each cost must be minimized while setting the paths correctly.
Algorithm Explanation
We will use Dijkstra’s algorithm to solve the problem.
Dijkstra’s algorithm is an algorithm that finds the shortest path in a weighted graph and proceeds as follows:
- Set the starting vertex and initialize the distance of this vertex to 0.
- Initialize the distance values of all other vertices to infinity.
- Select the vertex with the least cost and update the distance values to its neighboring vertices.
- Repeat the above process for all vertices. Ultimately, the minimum cost for each vertex is calculated.
C# Implementation
Now, let’s implement Dijkstra’s algorithm in C#.
First, we will reference the necessary libraries and use an adjacency list to represent the graph.
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
int n = 5; // Number of vertices
int m = 7; // Number of edges
List> edges = new List>()
{
Tuple.Create(1, 2, 2),
Tuple.Create(1, 3, 3),
Tuple.Create(2, 3, 1),
Tuple.Create(2, 4, 5),
Tuple.Create(3, 4, 1),
Tuple.Create(3, 5, 5),
Tuple.Create(4, 5, 2)
};
int start = 1; // Starting vertex
var result = Dijkstra(n, m, edges, start);
Console.WriteLine(string.Join(" ", result));
}
static int[] Dijkstra(int n, int m, List> edges, int start)
{
// Initialize graph
List>> graph = new List>>(n + 1);
for (int i = 0; i <= n; i++)
{
graph.Add(new List>());
}
// Add edges
foreach (var edge in edges)
{
graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));
}
// Initialize distances
int[] distance = new int[n + 1];
bool[] visited = new bool[n + 1];
for (int i = 1; i <= n; i++) distance[i] = int.MaxValue;
// Starting vertex
distance[start] = 0;
PriorityQueue> pq = new PriorityQueue>();
pq.Enqueue(Tuple.Create(0, start));
while (pq.Count > 0)
{
var current = pq.Dequeue();
int dist = current.Item1;
int node = current.Item2;
if (visited[node]) continue;
visited[node] = true;
foreach (var neighbor in graph[node])
{
int newDist = dist + neighbor.Item2;
if (newDist < distance[neighbor.Item1])
{
distance[neighbor.Item1] = newDist;
pq.Enqueue(Tuple.Create(newDist, neighbor.Item1));
}
}
}
return distance[1..]; // Return distances excluding start vertex
}
}
// Define priority queue class
public class PriorityQueue
{
List elements = new List();
public int Count => elements.Count;
public void Enqueue(T item)
{
elements.Add(item);
var index = elements.Count - 1;
while (index > 0)
{
var parentIndex = (index - 1) / 2;
if (Compare(elements[index], elements[parentIndex]) >= 0) break;
Swap(index, parentIndex);
index = parentIndex;
}
}
public T Dequeue()
{
var lastIndex = elements.Count - 1;
var firstElement = elements[0];
elements[0] = elements[lastIndex];
elements.RemoveAt(lastIndex);
--lastIndex;
int index = 0;
while (true)
{
var leftChildIndex = index * 2 + 1;
var rightChildIndex = index * 2 + 2;
int smallestChildIndex;
if (leftChildIndex > lastIndex) break;
if (rightChildIndex > lastIndex) smallestChildIndex = leftChildIndex;
else smallestChildIndex = Compare(elements[leftChildIndex], elements[rightChildIndex]) < 0 ? leftChildIndex : rightChildIndex;
if (Compare(elements[index], elements[smallestChildIndex]) <= 0) break;
Swap(index, smallestChildIndex);
index = smallestChildIndex;
}
return firstElement;
}
void Swap(int indexA, int indexB)
{
var temp = elements[indexA];
elements[indexA] = elements[indexB];
elements[indexB] = temp;
}
int Compare(T a, T b)
{
// Custom comparison logic needs to be implemented here
// For example, for Tuple
return a.Item1.CompareTo(b.Item1);
}
}
Algorithm Analysis
Using the above algorithm, the time complexity is O((N + M) log N).
Here, N is the number of vertices, and M is the number of edges.
Dijkstra’s algorithm is generally efficient,
and is effective in finding the minimum cost in many cases.
However, it should be noted that all edge weights must not be negative.
Conclusion
In this tutorial, we examined Dijkstra’s algorithm to solve the minimum cost path problem using C#.
We defined the problem, explained the algorithm, and gradually implemented the actual code.
Since such problems frequently appear in coding tests, it is important to practice and understand them thoroughly.
I hope this article helps in your preparation for coding tests.