Thuật toán Dijkstra trong C# Tìm Đường Ngắn Nhất Trong Đồ Thị

using System;
using System.Collections.Generic;

class Graph
{
    private int vertices;
    private List<Tuple<int, int>>[] adjacencyList;

    // Khởi tạo đồ thị
    public Graph(int v)
    {
        vertices = v;
        adjacencyList = new List<Tuple<int, int>>[v];
        for (int i = 0; i < v; ++i)
            adjacencyList[i] = new List<Tuple<int, int>>();
    }

    // Thêm cạnh vào đồ thị
    public void AddEdge(int u, int v, int weight)
    {
        adjacencyList[u].Add(new Tuple<int, int>(v, weight));
        adjacencyList[v].Add(new Tuple<int, int>(u, weight)); // Nếu đồ thị là vô hướng
    }

    // Hàm Dijkstra để tìm đường đi ngắn nhất
    public void Dijkstra(int src)
    {
        // Tạo một mảng để lưu khoảng cách từ src đến tất cả các đỉnh khác
        int[] dist = new int[vertices];

        // Mảng boolean để đánh dấu các đỉnh đã được xử lý
        bool[] sptSet = new bool[vertices];

        // Khởi tạo tất cả các khoảng cách là vô cùng và sptSet[] là false
        for (int i = 0; i < vertices; i++)
        {
            dist[i] = int.MaxValue;
            sptSet[i] = false;
        }

        // Khoảng cách từ nguồn đến chính nó là 0
        dist[src] = 0;

        // Duyệt tất cả các đỉnh
        for (int count = 0; count < vertices - 1; count++)
        {
            // Lấy đỉnh có khoảng cách nhỏ nhất trong các đỉnh chưa được xử lý
            int u = MinDistance(dist, sptSet);

            // Đánh dấu đỉnh u là đã xử lý
            sptSet[u] = true;

            // Cập nhật giá trị khoảng cách của các đỉnh lân cận của đỉnh u
            foreach (var neighbor in adjacencyList[u])
            {
                int v = neighbor.Item1;
                int weight = neighbor.Item2;

                // Cập nhật dist[v] nếu không có trong sptSet và có đường đi ngắn hơn thông qua u
                if (!sptSet[v] && dist[u] != int.MaxValue && dist[u] + weight < dist[v])
                {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // In ra khoảng cách từ src đến tất cả các đỉnh
        PrintSolution(dist);
    }

    // Hàm để tìm đỉnh có khoảng cách nhỏ nhất trong các đỉnh chưa được xử lý
    private int MinDistance(int[] dist, bool[] sptSet)
    {
        int min = int.MaxValue, minIndex = -1;

        for (int v = 0; v < vertices; v++)
        {
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    // Hàm để in ra kết quả
    private void PrintSolution(int[] dist)
    {
        Console.WriteLine("Đỉnh\tKhoảng cách từ nguồn");
        for (int i = 0; i < vertices; i++)
        {
            Console.WriteLine(i + "\t" + dist[i]);
        }
    }

    static void Main(string[] args)
    {
        Graph g = new Graph(9);

        g.AddEdge(0, 1, 4);
        g.AddEdge(0, 7, 8);
        g.AddEdge(1, 2, 8);
        g.AddEdge(1, 7, 11);
        g.AddEdge(2, 3, 7);
        g.AddEdge(2, 8, 2);
        g.AddEdge(2, 5, 4);
        g.AddEdge(3, 4, 9);
        g.AddEdge(3, 5, 14);
        g.AddEdge(4, 5, 10);
        g.AddEdge(5, 6, 2);
        g.AddEdge(6, 7, 1);
        g.AddEdge(6, 8, 6);
        g.AddEdge(7, 8, 7);

        g.Dijkstra(0);
    }
}