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

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

file input thuat toan Dijkstra

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];    
        
}
Bạn thấy bài viết này như thế nào?: 
Average: 8.4 (11 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Tập tành Working With Domain Access Module in Drupal 7.x

Tập tành Working With Domain Access Module in Drupal 7.x

Installation steps: 1. Download and install the Domain Access module using this link

Nâng cấp Drupal User Profiles với Profile2

Nâng cấp Drupal User Profiles với Profile2

Drupal 7 has made it easy for you to allow your site users to share information about themselves. User accounts are now "entities" which means that you can add fields to them, just as with content.

Apple

Cổ phiếu của Apple cán mốc 700 USD

Ngay sau thông tin iPhone 5 đã tẩu tán được 2 triệu đơn đặt hàng chỉ trong vòng 24 giờ đồng hồ, cổ phiếu của Apple đã tiếp tục tăng và cán mốc 700 USD/ cổ phiếu.

Công ty diệt chuột T&C

 

Diet con trung