//迪杰斯特拉算法
#include <iostream>
using namespace std;

#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;

int* D = new int[MVNum];
bool* S = new bool[MVNum];
int* Path = new int[MVNum];

typedef struct {
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
}AMGraph;

int LocateVex(AMGraph G, VerTexType v) {
    for (int i = 0;i < G.vexnum;++i) {
        if (G.vexs[i] == v)
            return i;
    }
    return -1;
}

void CreateUDN(AMGraph& G) {
    int i, j, k;
    cout << "请输入总顶点数，总边数，以空格隔开:";
    cin >> G.vexnum >> G.arcnum;
    cout << endl;

    cout << "输入点的名称:，如a" << endl;

    for (i = 0;i < G.vexnum;++i) {
        cout << "请输入第" << (i + 1) << "个点的名称:";
        cin >> G.vexs[i];
    }
    cout << endl;
    for (i = 0;i < G.vexnum;++i) {
        for (j = 0;j < G.vexnum;++j)
            G.arcs[i][j] = MaxInt;
    }
    cout << "输入边依附的顶点及权值，如a b 7" << endl;
    for (k = 0;k < G.vexnum;++j) {
        VerTexType v1, v2;
        ArcType w;
        cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = G.arcs[i][j];
    }
}

void ShortestPath_DIJ(AMGraph G, int v0) {
    int v, i, w, min;
    int n = G.vexnum;

    for (v = 0;v < n;v++) {
        S[v] = false;
        D[v] = G.arcs[v0][v];
        if (D[v] < MaxInt) Path[v] = v0;
        else Path[v] = -1;
    }
    S[v0] = true;
    D[v0] = 0;
    for (i = 1;i < n;++i) {
        min = MaxInt;
        for (w = 0;w < n;++w) {
            if (!S[w] && D[w] < min) {
                v = w;
                min = D[w];
            }
        }
        S[v] = true;
        for (w = 0;w < n;w++) {
            if (!S[w] && D[v] + G.arcs[v][w] < D[w])
                D[w] = D[v] + G.arcs[v][w];
            Path[w] = v;
        }
    }
}

void DisplayPath(AMGraph G, int begin, int temp) {
    if (Path[temp] != -1) {
        DisplayPath(G, begin, Path[temp]);
        cout << G.vexs[Path[temp]] << "-->";
    }
}

void main() {
    cout << "迪杰斯特拉算法" << endl;
    AMGraph G;
    int i, j, num_start, num_destination;
    VerTexType start, destination;
    CreateUDN(G);
    cout << endl;
    cout << "无向网G创建完成！" << endl;

    for (i = 0;i < G.vexnum;++i) {
        for (j = 0;j < G.vexnum;++j) {
            if (j != G.vexnum - 1) {
                if (G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] << "\t";
                else
                    cout << "~" << "\t";
            }
            else {
                if (G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] << endl;
                else    cout << "~" << endl;
            }
        }
    }
    cout << endl;
    cout << "请依次输入起始点、终点名称：";
    cin >> start >> destination;
    num_start = LocateVex(G, start);
    num_destination = LocateVex(G, destination);
    ShortestPath_DIJ(G, num_start);
    cout << endl << "最短路径为：";
    DisplayPath(G, num_start, num_destination);
    cout << G.vexs[num_destination] << endl;
}