Floyd

#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();// lay du lieu tu file
void input_B_E(int &a, int &b); //nhap vao dinh dau va cuoi
void output(int a, int b);//Xuat ket qua tu file ra
void Floyd (int a, int b);//thuat toan Floyd
void Menu(int &select);
item tongthiethai(); //tong quang duong di cua moi dinh (thay the cho vo cung trong ma tran trong so)

Graph Gr;
int *Len;//Gia tri nho nhat tu a -> i. Len1 danh dau do dai.
int **P;//truy vet
int **A;

int main()
{
    Graph Gr;
    input_file();
    int a, b, *P, i, select = 1;
    while (select)
    {
        cout<<endl<<"-----Thuat toan Floyd-----"<<endl;
        input_B_E(a, b);
        Floyd(a, b);
        output(a, b);
        Menu(select);
        if (!select) break;
    }
    return 0;
}

void input_file()   // nhap ma tran ke tu file
{
    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];
    Len = new int [Gr.n];
    P = new int *[Gr.n];
    A = new int *[Gr.n];
    for (int i=0; i<Gr.n; i++)
    {
        P[i] = new int [Gr.n];
        A[i] = new int [Gr.n];
        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(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(int a, int b)
{
    cout<<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;
    cout<<"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();
    }
    cout<<s<<endl;
}

//tong quang duong di cua moi dinh (thay the cho vo cung trong ma tran trong so)
item tongthiethai()
{
    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<<"Tiep tuc (1/0) ?";
    cin >> select;
}

void Floyd (int a, int b)
{
    int max = tongthiethai();
    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++)  // lap n lan
    {
        for (int i=0; i<Gr.n; i++)  // thay doi do dai duong di cua cac dinh
            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 ;
                }
    }
}