Giải thuật tìm đường đi ngắn nhất

// Mảng lưu dữ liệu đồ thị
int[,] A;
// Mảng lưu đường đi
int[] L;
// Điểm đi, điểm đến
int source, dest;
// Số đỉnh của đồ thị
int n;
// Mảng đánh dấu các đỉnh đã đi qua
int[] Tick;
// Giá trị đường đi ngắn nhất
int minLength = MAXINT;
// Các đỉnh đã đi qua
string minPath = "";
        
void InitializeBFS()
{
    L = new int[n + 1];
    Tick = new int[n + 1];
    source = Convert.ToInt16(txtSource.Text);
    dest = Convert.ToInt16(txtDest.Text);
            
    for (int i = 1; i <= n; i++)
    {
        Tick[i] = 0;
        L[i] = 0;
    }
    Tick[source] = 1;
    L[1] = source;
}

void SaveResult(int edge)
{
    string path = source.ToString() + " -> ";
    int length = 0;
    for (int i = 2; i <= edge; i++)
    {
        path = path + L[i].ToString() + " -> ";
        length = length + A[L[i - 1], L[i]];
    }
    if (length < minLength)
    {
        minLength = length;
        minPath = path;
    }
}

// Hàm đệ quy tìm mọi đường đi ngắn nhất giữa hai đỉnh
void TryBFS(int edge)
{
    if (L[edge] == dest)
    {
        // Mảng L là mảng lưu kết quả đường đi
        SaveResult(edge);
    }
    else
    {
        for (int i = 1; i <= n; i++)
            if (A[L[edge], i] > 0 && Tick[i] == 0)
            {
                L[edge + 1] = i;
                Tick[i] = 1;
                TryBFS(edge + 1);
                L[edge + 1] = 0;
                Tick[i] = 0;
            }
    }
}

int[] d;
int[] Trace;
void InitializeFord_Bellman()
{
    d = new int[n + 1];
    Trace = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        d[i] = MAXINT;
        for (int j = 1; j <= n; j++)
        {
            if (A[i, j] == 0 && i != j)
                A[i, j] = MAXINT;
        }
    }
    d[source] = 0;
}

void Ford_Bellman()
{
    bool isStop;
    for (int i = 1; i < n; i++)
    {
        isStop = true;
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++)
            {
                if (A[u, v] + d[u] < d[v])
                {
                    d[v] = d[u] + A[u, v];
                    Trace[v] = u;
                    isStop = false;
                }
            }

        if (isStop) break;
    }
}

string PrintResult()
{
    string res = "";
    if (d[dest] == MAXINT)
    {
        res = "Không có đường đi từ " + source + "đến " + dest;
    }
    else
    {
        int path = d[dest];
        while (dest != source)
        {
            res += dest + "<--";
            dest = Trace[dest];
        }
        res += source + ": " + path;
    }
    return res;
}

string Dijkstra(int[,] A, int n, int src, int des)
{
int[] DanhDau = new int[n + 1];
int[] Nhan = new int[n + 1];
int[] Truoc = new int[n + 1];
int XP, min, i;
for (i = 1; i <= n; i++)
{
    Nhan[i] = MAXINT;
    DanhDau[i] = 0;
    Truoc[i] = src;
}
Nhan[src] = 0;
DanhDau[src] = 1;
XP = src;
while (XP != des)
{
    for (int j = 1; j <= n; j++)
        if (A[XP, j] > 0 && Nhan[j] > A[XP, j] + Nhan[XP] && DanhDau[j] == 0)
        {
            Nhan[j] = A[XP, j] + Nhan[XP];
            Truoc[j] = XP;
        }
    min = MAXINT;
    for (int j = 1; j <= n; j++)
        if (min > Nhan[j] && DanhDau[j] == 0)
        {
            min = Nhan[j];
            XP = j;
        }
    DanhDau[XP] = 1;
}
            
// Truy vết đường đi và in kết quả
string[] temp = new string[n + 1];
temp[0] = des.ToString();
temp[1] = Truoc[des].ToString();
i = Truoc[des];
int count = 2;
while (i != src)
{
    i = Truoc[i];
    temp[count] = i.ToString();
    count++;
}
string res = "";
for (i = count - 1; i >= 1; i--)
    res += temp[i] + " --> ";
res += temp[0] + ": " + Nhan[des];

return res;
}