[数据结构与算法]数据结构实验7《基于Dijsktra算法的最短路径求解》

（visual studio 2019可运行）
输入及输出要求见《数据结构C语言(第二版)》严蔚敏版
【本文仅用于啥都看不懂还想交作业选手】

加了一点输入异常的反馈

基于基于Dijsktra算法的最短路径求解 - 简书改动

（这是一个我终于明白并不需要一次性统一输出的故事）

#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
typedef int Status;
//用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767                        //表示极大值，即∞
#define MVNum 100                           //最大顶点数 
typedef char VerTexType;                //假设顶点的数据类型为字符型 
typedef int ArcType;                    //假设边的权值类型为整型 
typedef struct {
    VerTexType vexs[MVNum];                   //顶点表 
    ArcType arcs[MVNum][MVNum];               //邻接矩阵 
    int vexnum;//图的总点数
    int arcnum;//图的总边数                    
}AMGraph;
int LocateVex(AMGraph G, VerTexType u)
{//存在则返回u在顶点表中的下标;否则返回-1
    int i;
    for (i = 0; i < G.vexnum; ++i)
        if (u == G.vexs[i])
            return i;
    return -1;
}
VerTexType OrigialVex(AMGraph G, int u)
{//存在则返回u在顶点表中的下标;否则返回-1
    return G.vexs[u];
}
Status CreateUDN(AMGraph& G) {
    //采用邻接矩阵表示法，创建无向网G 
    cin >> G.vexnum;  //输入总顶点数
    cin >> G.arcnum;  //输入总边数 
    int i, j, k, w;
    VerTexType v1, v2;
    for (i = 0; i < G.vexnum; ++i)
        cin >> G.vexs[i];                           //依次输入点的信息 
    for (i = 0; i < G.vexnum; ++i)  //初始化邻接矩阵，边的权值均置为极大值
        for (j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;
    for (k = 0; k < G.arcnum; ++k) {                     //构造邻接矩阵 
        cin >> v1 >> v2 >> w;                                 //输入一条边依附的顶点及权值 
        i = LocateVex(G, v1);  j = LocateVex(G, v2);  //确定v1和v2在G中的位置
        G.arcs[i][j] = w; //边<v1, v2>的权值置为w 
        G.arcs[j][i] = G.arcs[i][j];              //置<v1, v2>的对称边<v2, v1>的权值为w 
    } 
    return OK;
}
Status CreateDN(AMGraph& G, int dian, int bian) {   //创建有向网G的邻接矩阵
    G.vexnum = dian;
    G.arcnum = bian;
    int i, j, k, w;
    VerTexType v1, v2;
    for (i = 0; i < G.vexnum; ++i)
        cin >> G.vexs[i];                           //依次输入点的信息 
    for (i = 0; i < G.vexnum; ++i)  //初始化邻接矩阵，边的权值均置为极大值
        for (j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;
    for (k = 0; k < G.arcnum; ++k) {                     //构造邻接矩阵 
        cin >> v1 >> v2 >> w;                                 //输入一条边依附的顶点及权值 
        i = LocateVex(G, v1);  j = LocateVex(G, v2);  //确定v1和v2在G中的位置
        G.arcs[i][j] = w; //边<v1, v2>的权值置为w  
    }
    return OK;
}
int D[MVNum], Path[MVNum],S[MVNum];

void ShortestPath_DIJ(AMGraph G, VerTexType V) {
    //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 
    int i, n, v, min, w;
    n = G.vexnum;                         //n为G中顶点的个数 
    int v0 = LocateVex(G, V);
    for (v = 0; v < n; ++v)
    {               //n个顶点依次初始化 
        S[v] = false;                   //S初始为空集 
        D[v] = G.arcs[v0][v];               //将v0到各个终点的最短路径长度初始化 
        if (D[v] < MaxInt)
            Path[v] = v0; //v0和v之间有弧，将v的前驱置为v0
        else
            Path[v] = -1;                //如果v0和v之间无弧，则将v的前驱置为-1 
    }
    S[v0] = true;                     //将v0加入S 
    D[v0] = 0;                            //源点到源点的距离为0 
    D[-1] = -1;              //出现异常顶点
    /*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/
    for (i = 1; i < n; ++i){                   //对其余n?1个顶点，依次进行计算 
        min = MaxInt;
        for (w = 0; w < n; ++w)
            if (!S[w] && D[w] < min)
            {
                v = w; min = D[w];
            }           //选择一条当前的最短路径，终点为v 
        S[v] = true;                          //将v加入S 
        for (w = 0; w < n; ++w)   //更新从v0出发到集合V?S上所有顶点的最短路径长度 
            if (!S[w] && (D[v] + G.arcs[v][w] < D[w])) {
                D[w] = D[v] + G.arcs[v][w];     //更新D[w] 
                Path[w] = v;                     //更改w的前驱为v 
            }
    }
}
void find(AMGraph G, int v,char A)
{
    int n = G.vexnum;
    if (Path[v] == -1||v==-1)
        return;
    else
    {
        find(G, Path[v],A);
        cout << OrigialVex(G, Path[v]) << " ";
    }
}
int main()
{
    char A, B;
    int a, b;
    while (cin >> a >> b && a && b) {
        AMGraph G;
        CreateDN(G, a, b);
        cin >> A;
        ShortestPath_DIJ(G, A);
        cin >> B;
        int n = LocateVex(G, B);
        cout << D[n] << endl;
        find(G, n,A);
        if (D[n] == -1)//异常查找
            cout << "wrong point!" << endl;
        else
            cout << B << endl;
    }
    return 0;
}