Cài đặt chương trình mô phỏng thuật toán Dijkstra bằng ngôn ngữ C/C++

Xem lại lý thuyết từ link sau

>> Cài đặt chương trình mô phỏng thuật toán Dijkstra bằng Pascal

file input.inp:

8
A B C D E F G H
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

Code ngay trong main

#include <stdio.h>
#include <stdlib.h>
#define INP "input.inp"
#define OUT "output.out"
 
int main() {
    FILE *fi = fopen(INP, "r");
    FILE *fo = fopen(OUT, "w");
    int n, a, b, i, sum = 0;
 
    // nhap du lieu tu file input
    fscanf(fi, "%d%d%d", &n, &a, &b);
    int G[n][n];
    int S[n], Len[n], P[n];
 
    // nhap ma tran va tinh gia tri vo cung (sum)
    for (i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            fscanf(fi, "%d", &G[i][j]);
            sum += G[i][j];
        }
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;                   // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;                       // danh sach cac diem da xet
        P[i] = a;                       // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;                         // dat do dai tu a -> a la 0
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            break;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j]) {
                i = j;
            }
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
 
    printf("done dijkstra\n");
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    printf("start find path\n");
 
    if (Len[b] > 0 && Len[b] < sum) {
        fprintf(fo, "Length of %d to %d is %d\n", a + 1, b + 1, Len[b]);
 
        // truy vet
        while (i != a) {
            fprintf(fo, "%d <-- ", i + 1);
            i = P[i];
        }
        fprintf(fo, "%d", a + 1);
    } else {
        fprintf(fo, "khong co duong di tu %d den %d\n", a + 1, b + 1);
    }
 
    printf("done find path\n");
 
    fclose(fi);
    fclose(fo);
 
    printf("done - open file output to see result\n");
    return 0;
}

Code theo từng hàm

– readData thực hiện đọc thông tin từ file input.

– dijkstra thực hiện thuật toán

– back thực hiện trả về chuỗi là đường đi tìm được

– outResult thực hiện in ra file output kết quả

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
 
#define INP "input.inp"
#define OUT "output.out"
 
// read data in file input
int readData(int ***G, int *n, int *a, int *b) {
    FILE *fi = fopen(INP, "r");
    if (fi == NULL) {
        printf("file input not found!\n");
        return 0;
    }
    printf("start read file\n");
 
    fscanf(fi, "%d %d %d", n, a, b);
 
    *G = (int **) malloc((*n) * sizeof(int));
    for (int i = 0; i < *n; i++) {
        (*G)[i] = (int *) malloc((*n) * sizeof(int));
        for (int j = 0; j < *n; j++) {
            int x;
            fscanf(fi, "%d", &x);
            (*G)[i][j] = x;
        }
    }
 
    fclose(fi);
    printf("done read file\n");
    return 1;
}
 
// thuat toan dijkstra
int dijkstra(int **G, int n, int a, int b, int P[]) {
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start dijkstra\n");
 
    int* Len = (int *) malloc(n * sizeof(int));
    int* S = (int *) malloc(n * sizeof(int));
 
    int sum = 0;            // gia tri vo cung
 
    // tinh gia tri vo cung (sum)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += G[i][j];
        }
    }
 
    // dat vo cung cho tat ca cap canh khong noi voi nhau
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && G[i][j] == 0)
                G[i][j] = sum;
        }
    }
 
    for (int i = 0; i < n; i++) {
        Len[i] = sum;       // khoi tao do dai tu a toi moi dinh la vo cung
        S[i] = 0;           // danh sach cac diem da xet
        P[i] = a;           // dat diem bat dau cua moi diem la a
    }
 
    Len[a] = 0;             // dat do dai tu a -> a la 0
 
    int i;
 
    // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
    //for (int k = 0; k < n; k++)
    while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
        for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
            if (!S[i] && Len[i] < sum)
                break;
 
        // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
        if (i >= n) {
            printf("done dijkstra\n");
            return 0;
        }
 
        for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
            if (!S[j] && Len[i] > Len[j])
                i = j;
        }
 
        S[i] = 1;                       // cho i vao danh sach xet roi
 
        for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
            if (!S[j] && Len[i] + G[i][j] < Len[j]) {
                Len[j] = Len[i] + G[i][j];      // thay doi len
                P[j] = i;                       // danh dau diem truoc no
            }
        }
    }
    printf("done dijkstra\n");
    return Len[b];
}
 
//  truy vet duong di
void back(int a, int b, int *P, int n, char *path) {
 
    //char *path = (char *) malloc((n * 10) * sizeof(char));
 
    /* Do mang tinh tu G[0][0] nen can giam vi tri
     di 1 don vi de tinh toan cho phu hop*/
    a--;
    b--;
 
    printf("start find path\n");
 
    int i = b;
    int point[n];   // danh sach cac dinh cua duong di
    int count = 0;
 
    /* Do ta dang tinh toan tu dinh 0 nen
     muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
 
    point[count++] = i + 1;
    while (i != a) {
        i = P[i];
        point[count++] = i + 1;
    }
 
    strcpy(path, "");
    char temp[10];
    for (i = count - 1; i >= 0; i--) {
        sprintf(temp, "%d", point[i]);
        strcat(path, temp);
 
        if (i > 0) {
            sprintf(temp, " --> ");
            strcat(path, temp);
        }
    }
 
    printf("done find path\n");
}
 
void outResult(int len, char* path) {
    FILE *fo = fopen(OUT, "w");
 
    if (len > 0) {
        fprintf(fo, "\nLength of %c to %c is %d\n", path[0],
                path[strlen(path) - 1], len);
    }
 
    fprintf(fo, "path: %s\n", path);
 
    fclose(fo);
}
 
int main() {
    int **G, n, a, b, len;
 
    if (readData(&G, &n, &a, &b) == 0) {
        return 0;
    }
 
    char *path = (char *) malloc((10 * n) * sizeof(char));
    int P[n];
 
    len = dijkstra(G, n, a, b, P);
 
    if (len > 0) {
        back(a, b, P, n, path);
        outResult(len, path);
    } else {
        char *path = (char *) malloc((n * 10) * sizeof(char));
        sprintf(path, "khong co duong di tu %d den %d\n", a, b);
        outResult(len, path);
    }
 
    printf("done - open file output to see result\n");
    return 0;
}

Code nâng cao

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <queue>
#include <stack>
#define INP "input.INP"
#define OUT "output.OUT"
using namespace std;

typedef int item;
typedef struct GRAPH
{
    char *name;    // ten cac dinh
    item **G;    // ma tran trong so
    int n;        // so phan tu cua do thi
} Graph;

void input_file(Graph &Gr);// lay du lieu tu file
void input_B_E(Graph Gr, int &a, int &b); //nhap vao dinh dau va cuoi
void output_file(Graph Gr);//Xuat ket qua tu file ra
void Menu(int &select); //menu chon thuat toan
int Dijkstra(Graph Gr, int a, int b);//thuat toan Dijkstra
int number_or_char(Graph Gr); //nhap vao kiem tra la ky tu hay so va tra ve vi tri cua dinh trong do thi
item tongthiethai(Graph Gr); //tong quang duong di cua moi dinh (thay the cho vo cung trong ma tran trong so)
string convert_to_string(int number);//chuyen so number sang chuoi
int floyd (Graph Gr, int a, int b);

int main()
{
    Graph Gr;
    input_file(Gr);
    int a, b, *P, i, select = 1;
    output_file(Gr);
    while (select)
    {
        Menu(select);
        switch (select)
        {
            case 1:
            {
                cout<<endl<<"-----Thuat toan Dijkstra-----"<<endl;
                input_B_E(Gr, a, b);
                Dijkstra(Gr, a, b);
                system("pause");
                break;
            }
            case 2:
            {
                cout<<endl<<"-----Thuat toan Floy-----"<<endl;
                input_B_E(Gr, a, b);
                floyd (Gr, a, b);
                system("pause");
                break;
            }
        }
        if (select == 3) break;
    }
    
    system("pause");
    return 0;
}

void input_file(Graph &Gr)
{
    ifstream inp(INP);
    if (inp == NULL)
    {
        cout<<"No found file input";
        return;
    }
    inp >> Gr.n ;
    
    Gr.name = new char [Gr.n];
    for (int i=0; i<Gr.n; i++)
        inp >> Gr.name[i];
    Gr.G = new int *[Gr.n];
    
    for (int i=0; i<Gr.n; i++)
    {
        Gr.G[i] = new int [Gr.n];
        for (int j=0; j<Gr.n; j++)
            inp >> Gr.G[i][j];
    }
    inp.close();
}

void input_B_E(Graph Gr, int &a, int &b)
{
    a = b = 0;
    cout<<endl<<"Cac dinh danh so tu 1 den "<<Gr.n<<".Hoac tu "<<Gr.name[0]<<" den "<<Gr.name[Gr.n-1]<<endl;
    cout<<"Nhap dinh bat dau : ";
    while (a<1 || a> Gr.n)
    {
        cin>>a;
        if (a<1 || a> Gr.n)
            cout<<"Khong hop le ! \nNhap lai dinh bat dau : ";
    }
    
    cout<<"Nhap dinh ket thuc : ";
    while (b<1 || b> Gr.n)
    {
        cin>>b;
        if (b<1 || b> Gr.n)
            cout<<"Khong hop le ! \nNhap lai dinh ket thuc : ";
    }
    a -- ;
    b -- ;
}

void output_file(Graph Gr)
{
    //ofstream out(OUT);
    fstream out;
    out.open(OUT, ios::out|ios::trunc);
    cout<<"Ma tran ke cua do thi"<<endl<<endl;
    out<<"Ma tran ke cua do thi"<<endl<<endl;
    for (int i=0; i<Gr.n; i++)
    {
        cout<<setw(2)<<Gr.name[i];
        out<<setw(2)<<Gr.name[i];
    }
    out<<endl<<endl;
    cout<<endl<<endl;
    for (int i=0; i<Gr.n; i++)
    {
        for (int j=0; j<Gr.n; j++)
        {
            cout<<setw(2)<<Gr.G[i][j];
            out<<setw(2)<<Gr.G[i][j];
        }
        cout<<endl;
        out<<endl;
    }
    out.close();
}

//tong quang duong di cua moi dinh (thay the cho vo cung trong ma tran trong so)
item tongthiethai(Graph Gr)
{
    item sum = 0;
    for (int i=0; i<Gr.n; i++)
        for (int j=0; j<Gr.n; j++)
            sum += Gr.G[i][j];
    return sum;
}

void Menu(int &select)
{
    cout<<endl<<"Moi ban chon thuat toan :"<<endl;
    cout<<"1: Thuat toan Dijkstra"<<endl;
    cout<<"2: Thuat toan Floyd"<<endl;
    cout<<"3: Thoat !"<<endl;
    cin >> select;
}

int Dijkstra(Graph Gr, int a, int b)
{
    fstream out;
    out.open(OUT, ios::out|ios::app);
    out<<endl<<"*****"<<endl;
    // Len[i] - Gia tri nho nhat tu a -> i. Len1 danh dau do dai.
    int Len[Gr.n];
    int S[Gr.n];//Danh dau dinh thuoc danh sach dac biet
    int P[Gr.n];//truy vet
    
    int max = tongthiethai(Gr);
    fill (Len,Len+Gr.n,max); //Gan duong di ban dau = vo cung
    fill (P,P+Gr.n,a);
    fill (S,S+Gr.n,0); //Danh sach dac biet
    Len[a] = 0;        // khoi tao do dai tu a->a = 0
    int i = a, dem = 0, space = 10;
    
    //in ra hang tieu de
    out<<setw(space/2)<<"TT |";
    for (int i=0; i<Gr.n; i++)
    {
        char s[100];
        sprintf(s,"%d%c%c%c",i+1,'(',Gr.name[i],')');
        out<<setw(space)<<s;
    }
    out <<endl;
    for (int i=0; i< (space/2) + Gr.n*10; i++)
        out<<"-";
    out<<endl;
    //ket thuc in ra hang tieu de
    
    //while S<>V
    for (int k=0; k<Gr.n; k++)
    {
        dem ++;
        char *s = new char [100];
        char vocung = '~' , gach[10] = "  -  ";
        out<<setw(space/2-2)<<dem<<" |";
        
        //tim do dai ngan nhat trong cac dinh        
        for (i=0; i<Gr.n; i++) // tim v thuoc (V-S) va Len[v] < vo cung
            if (!S[i] && Len[i] != max)
                break;
        for (int j = i+1 ; j<Gr.n; j++)    // tim dinh co Len min
            if (!S[j] && Len[j] < Len[i])
                i = j;
        S[i] = 1;    
        
        //----------In ra gia tri moi lan lap------------
        if (dem > 0)
            for (int j=0; j<Gr.n; j++)
            {
                char temp[100];
                strcpy(s," ");
                if (dem >1 && j != i && S[j])
                    sprintf(s,"%c",'-');
                else
                {
                    if (j == i || (dem == 1 && j == a))
                        strcat(s,"*");
                    strcat(s,"[");
                    if ( j != i && !S[j] && Len[j] == max)
                        sprintf(temp,"%c,",vocung);
                    else
                        sprintf(temp,"%d,",Len[j]);
                    strcat(s,temp);
                    if (j!=a && k==0)
                        sprintf(temp, "%c", vocung);
                    else sprintf(temp, "%d", P[j]+1);    
                    strcat(s,temp);
                    strcat(s,"]");
                    
                }
                out<<setw(space)<<s;
            }
        
        //----------Ket thuc In ra gia tri moi lan lap------------
        
        //--------Tinh do dai tu dinh dang xet toi cac dinh tiep
        
        for (int j = 0; j<Gr.n; j++) //thay doi do dai neu co
        {
            if (!S[j] && Gr.G[i][j])
                if (Len[i] + Gr.G[i][j] < Len[j])
                {
                    Len[j] = Len[i] + Gr.G[i][j];
                    P[j] = i; //truy vet
                }
        }    
        out<<endl;            
    }
    
    //Ket luan duong di
    
    out<<endl<<"Do dai ngan nhat cua duong di tu "<<a+1<<"("<<Gr.name[a]<<")"
        <<" den "<<b+1<<"("<<Gr.name[b]<<")"<<" la "<<Len[b]<<endl;
    out<<"Qua trinh duong di: ";
    i = b;
    char *s, *temp;
    s = new char [Gr.n*10];
    temp = new char [10];
    sprintf(s,"%d",i+1);
    while (i != a)
    {
        sprintf(temp,"%s"," --> ");
        strcpy(s,strcat(temp,s));
        sprintf(temp,"%d",P[i] +1);
        strcpy(s,strcat(temp,s));
            
        i = P[i];
    }    
    out<<s<<endl;
    cout<<"Hoan thanh ! Mo file output.out de xem ket qua !";
    out.close();
    return Len[b];
}

int floyd (Graph Gr, int a, int b)
{
    fstream out;
    out.open(OUT, ios::out|ios::app);
    int max = tongthiethai(Gr);
    int A[Gr.n][Gr.n], P[Gr.n][Gr.n];
    for (int i=0; i<Gr.n; i++)
        for (int j=0; j<Gr.n; j++)
        {
            if (Gr.G[i][j])
                A[i][j] = Gr.G[i][j];
            else A[i][j] = max;
            P[i][j] = -1;
        }
        
    for (int k=0; k<Gr.n; k++)
    {
        out<<endl<<"Buoc thu "<<k<<endl;
        out<<setw(2*Gr.n)<<"A"<<setw(15+4*Gr.n)<<"P"<<endl;
        for (int i=0; i<Gr.n; i++)
        {
            
            for (int j=0; j<Gr.n; j++)
            {
                char *temp = new char [50];
                if (A[i][j] == max)
                    sprintf(temp,"%c",'~');
                else
                    sprintf(temp,"%d",A[i][j]);
                
                out<<setw(4)<<temp;
            }
                
            out<<setw(15)<<" ";
            for (int j=0; j<Gr.n; j++)
                out<<setw(4)<<P[i][j] + 1;
            out<<endl;
        }
            
        
        for (int i=0; i<Gr.n; i++)
            for (int j=0; j<Gr.n; j++)
                if (A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = k ;
                }    
    }
    
    out<<endl<<"Do dai ngan nhat cua duong di tu "<<a+1<<"("<<Gr.name[a]<<")"<<" den "<<b+1<<"("<<Gr.name[b]<<")"<<" la "<<A[a][b]<<endl;
    out<<"Qua trinh duong di: ";
    
    //truy vet
    char *s, *temp;
    s = new char [Gr.n*10];
    temp = new char [10];
    stack <item> S1;
    stack <item> S2;
    S1.push(a); //danh sach nap cac dinh vao
    S1.push(b); //danh sach xuat cac dinh ra
    int dich, tg;
    while (!S1.empty())
    {
        dich = S1.top(); //dich = phan tu dau tien
        S1.pop();         // dua phan tu do ra
        S2.push(dich); //cho vao danh sach xuat
        if (!S1.empty()) //trong khi S1 ko rong thi tiep tuc tim cac dinh
        {
            tg = S1.top();
            while (P[tg][dich] != -1) //tim cac dinh di tu tg den dich
            {
                S1.push(P[tg][dich]);
                tg = S1.top();
            }
        }
    }
    
    sprintf(s,"%d",S2.top()+1);
    S2.pop();
    
    while (!S2.empty())
    {
        sprintf(temp,"%s%d"," --> ",S2.top()+1);
        strcat(s,temp);
        S2.pop();
    }
    
    out<<s<<endl;
    cout<<"Hoan thanh ! Mo file output.out de xem ket qua !";
    out.close();
    
    return A[a][b];    
        
}