Scribd Logo
Upload

Welcome to Scribd!

  • 26 views

    Thuat Toan Tim Kiem Tot Nhat

    Uploaded by

    Tân Lai
    The document contains C++ code that implements Dijkstra's algorithm to find the shortest path between two nodes (s and e) in a graph. It includes functions to scan input data from a file defining the graph, store the graph data in maps and lists, run Dijkstra's algorithm to iteratively find the shortest path, and output the results. Dijkstra's algorithm uses a priority queue to efficiently select the node with the lowest distance from s at each step and explore its neighbors until reaching the target node e.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    Thuat Toan Tim Kiem Tot Nhat

    Uploaded by

    Tân Lai
    26 views2 pages
    The document contains C++ code that implements Dijkstra's algorithm to find the shortest path between two nodes (s and e) in a graph. It includes functions to scan input data from a file defining the graph, store the graph data in maps and lists, run Dijkstra's algorithm to iteratively find the shortest path, and output the results. Dijkstra's algorithm uses a priority queue to efficiently select the node with the lowest distance from s at each step and explore its neighbors until reaching the target node e.

    Original Title

    thuat-toan-tim-kiem-tot-nhat

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains C++ code that implements Dijkstra's algorithm to find the shortest path between two nodes (s and e) in a graph. It includes functions to scan input data from a file defining the graph, store the graph data in maps and lists, run Dijkstra's algorithm to iteratively find the shortest path, and output the results. Dijkstra's algorithm uses a priority queue to efficiently select the node with the lowest distance from s at each step and explore its neighbors until reaching the target node e.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    26 views2 pages

    Thuat Toan Tim Kiem Tot Nhat

    Uploaded by

    Tân Lai
    The document contains C++ code that implements Dijkstra's algorithm to find the shortest path between two nodes (s and e) in a graph. It includes functions to scan input data from a file defining the graph, store the graph data in maps and lists, run Dijkstra's algorithm to iteratively find the shortest path, and output the results. Dijkstra's algorithm uses a priority queue to efficiently select the node with the lowest distance from s at each step and explore its neighbors until reaching the target node e.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    You are on page 1of 2

    #include<bits/stdc++.

    h>
    using namespace std;
    char s, e;
    unordered_map<char,int>Diem; //first: diem, second: tr?ng
    string DuongDi = "";
    list<char> DiemNoi[100]; // DS diem noi toi cac diem khac
    priority_queue<pair<int,char>,vector<pair<int,char>>,greater<pair<int,char>>>
    DanhSach;

    void RunAlgorithm(){
    fstream f;
    f.open("result.txt", ios::out);
    f<<"Phat trien TT Trang thai ke Danh sach L\n";
    while(s != e){
    DuongDi += s;DuongDi += "->";
    f<<" "<< s << "-" << Diem[s] <<" ";
    cout<<" "<< s << "-" << Diem[s] <<" ";
    for(auto i:DiemNoi[s]){
    DanhSach.push({Diem[i],i});
    f<< i << "-" << Diem[i]<<" ";
    cout<< i << "-" << Diem[i]<<" ";
    }
    f<< " ";
    cout<< " ";

    priority_queue<pair<int,char>,vector<pair<int,char>>,greater<pair<int,char>>>
    tmp = DanhSach;
    while(tmp.size()){
    pair<int,int> trunggian = tmp.top(); tmp.pop();
    f<<(char)trunggian.second<< "-" << trunggian.first<<" ";
    cout<<(char)trunggian.second<< "-" << trunggian.first<<" ";
    }
    s = DanhSach.top().second;DanhSach.pop();
    f<<endl;
    cout<<endl;
    }
    f<<" "<< s << "-" << Diem[s] <<" TTKT-DUNG\n";
    cout<<" "<< s << "-" << Diem[s] <<" TTKT-DUNG\n";
    DuongDi += e;
    f<<DuongDi;
    cout<<DuongDi;
    f.close();
    }

    void ScanFile(){
    fstream f;
    f.open("data.txt", ios::in);
    if (f.fail())
    {
    cout << "Failed to open this file!";
    return;
    }
    string line;
    int tmp = 0; // 0: trong so; 1: noi voi cac diem
    while (!f.eof())
    {
    getline(f, line);
    if(line.substr(0,4) == "TTD ") s = line.back();
    else if(line.substr(0,4) == "TTKT") e = line.back();
    else {
    int trongso = atoi(line.substr(line.find(",")+1,line.find(")")-
    1).c_str()); // atoi: ham chuyen doi day char sang so, c_str: ham chuyen string
    sang day char
    int diem = line.find("(")+1; // vi tri cua diem A trong data
    Diem[line[diem]] = trongso;
    cout<<line[diem]<< " "<< trongso<<" ";
    int vtDau = line.find(">")+1, vtCuoi = line.size();
    if(vtDau!=0){
    for(int i= vtDau; i<vtCuoi; i++)
    {
    if(line[i] != ' ')
    DiemNoi[line[diem]].push_back(line[i]),cout<<line[i]<<" ";
    }
    }
    cout<<"\n";
    }
    }
    f.close();
    }

    int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ScanFile();
    RunAlgorithm();
    }

    You might also like