Dijkstra

#include 
#include 

using namespace std;

const int MAX = 32667;


int *Distance = new int[100];
int *path = new int[100];
bool *s = new bool[100];

// Adjacency Matrix
struct AMGraph
{
    int m_vexnum;
    int m_arcnum;
    char m_vexname[100];
    int m_weight[100][100];

};

//  Find the index of the point in the array by its name
int locateVax(AMGraph &AMG, char vexname)
{
    for(int i = 0; i < AMG.m_vexnum; i++)
    {
        if(AMG.m_vexname[i] == vexname)
            return i;
    }
    return -1;
}

// creat and init function
void CreateAMGraph(AMGraph &AMG)
{
    cout << "pls input your vexnum and arcnum " << endl;
    cin >> AMG.m_vexnum >> AMG.m_arcnum;
    cout << "pls input the vexname " << endl;

    for(int i = 0; i < AMG.m_vexnum; i++)
    {
        cout << "the name " << i+1 << ": " << endl;
        cin >> AMG.m_vexname[i];
    }

    for(int i = 0; i < AMG.m_vexnum; i++)
    {
        for(int j = 0; j < AMG.m_vexnum; j++)
        {
            AMG.m_weight[i][j] = MAX;
        }
    }

    cout << "pls input the arcweight as 'a b 1' " << endl;
    for(int i = 0; i < AMG.m_arcnum; i++)
    {
        char vexname1, vexname2;
        int weight;
        cout << "the weight " << i+1 << " :" << endl;
        cin >> vexname1 >> vexname2 >> weight;
        int m = locateVax(AMG, vexname1);
        int n = locateVax(AMG, vexname2);
        // 双向图
        AMG.m_weight[m][n] = weight;
        AMG.m_weight[n][m] = AMG.m_weight[m][n];
    }
}


void Dijkstra(AMGraph &AMG, char startVex)
{
    int startAdd = locateVax(AMG, startVex);
    for(int i = 0; i < AMG.m_vexnum; i++)
    {
        s[i] = false;
        Distance[i] = AMG.m_weight[startAdd][i];
        if(Distance[i] < MAX)
        {
            path[i] = startAdd;
        }
        else
        {
            path[i] = -1;
        }
    }
    s[startAdd] = true;
    Distance[startAdd] = 0;         
    for(int i = 1; i < AMG.m_vexnum; i++)
    {
        int min = MAX;
        for(int j = 0; j < AMG.m_vexnum; j++)
        {
            if(!s[j] && Distance[i] < min)
            {
                i = j;
                min = Distance[i];
            }
        }

        s[i] = true;
        for(int k = 0; k < AMG.m_vexnum; k++)
        {
            if(!s[k] && Distance[k] > AMG.m_weight[i][k] + Distance[i])
            {
                Distance[k] = AMG.m_weight[i][k] + Distance[i];
                path[k] = i;
            }
        }
    }
}


void ShowPath(AMGraph AMG, int startVexAdd, int endVexAdd)
{
    if(path[endVexAdd] != -1)
    {
        ShowPath(AMG, startVexAdd, path[endVexAdd]);
        cout << AMG.m_vexname[path[endVexAdd]] << "->";
    }
}


void test()
{
    AMGraph mygraph;
    CreateAMGraph(mygraph);
    char startVex, endVex;
    cout << "pls input the startVex and endVex name as 'a b ' " << endl;
    cin >> startVex >> endVex;
    int startVexAdd = locateVax(mygraph, startVex);
    int endVexAdd = locateVax(mygraph, endVex);
    Dijkstra(mygraph, startVex);
    ShowPath(mygraph, startVexAdd, endVexAdd);
    cout << endVex << endl;
    
    delete[] Distance;
    delete[] path;
    delete[] s;
}

int main()
{
    test();
    system("pause");
    return 0;
}