1708: 数据结构-Dijskra(迪杰斯特拉)最短路径算法(C++)---如果有答案错误50分可以看一下

解题思路:

解题思路:对于最短路问题，最典型的即迪级斯特拉算法，运用该算法可以解决本体，具体详解我结合着代码给出了相应批注

注意事项:对于本题而言，除了考虑最短路问题，还需要注意输出格式以及没有通路即为“-1”这两个注意事项，否则会出现答案错误（50）分的情况

参考代码:

#include <bits/stdc++.h>
#define max 65535
#define size 1000
#define join 65534
#define ini 65532
using namespace std;
typedef int Para[size];//存路径节点
typedef int Short[size];//存路径长度
int ori;//起始顶点
typedef struct
{
    // 顶点表
    int vex[size];
    // 邻接矩阵
    int arc[size][size];
    // 顶点数，边数
    int numvex, numedge;
} MGroup;
void createGroup(MGroup* G);
void Dijisktra(MGroup* G, int v0, Para* P, Short* D);
void Search_for(MGroup* G, Para p, Para d);
int main()
{
    MGroup* G = new MGroup();
    createGroup(G);
    Para P;
    Short D;
    fill(D, D + G->numvex, max);
    Dijisktra(G,ori, &P, &D);
    Search_for(G, P, D);
    return 0;
}
void Search_for(MGroup* G,Para p,Para d)
{
    vector<int>pt;
    for (int i=0;i<G->numvex;i++)
    {   if(i!=ori)
            pt.push_back(d[i]);
    }
    vector<int>::iterator it;
    for (it = pt.begin(); it != pt.end() - 1; it++)
    {
        if (*it != max)//这里一定要注意
            cout << *it << " ";
        else//判断特殊条件
            cout << "-1" << " ";
    }
    if (pt.back() != max)
        cout << pt.back();
    else
        cout << "-1";
}

void createGroup(MGroup* G)
{
    int i, j, k, w;
    // 创建图的过程就是将顶点表填入相应数值
    cin >> G->numvex>>ori;
    //cout << "请输入顶点信息";
    for (i = 0; i < G->numvex; i++)
    {
        G->vex[i] = i;
    }

    for (int i = 0; i < G->numvex; i++) // 再设计最小生成树时，一定要初始化，不然容易弄混淆,或者定义一个参数作为生成树的标志
        fill(G->arc[i], G->arc[i] + (G->numvex), max);//fill将每一项初始成max(65535)
    //cout << "请输入边信息，依次是行，列，权值" << endl;
    for (i = 0; i < G->numvex; i++)
    {
        for (int j = 0; j < G->numvex; j++)
        {
            int value;
            cin >> value;
            if (value)
            {
                G->numedge++;
                G->arc[i][j] = value;
                // 无向图是对称图
                //G->arc[j][i] = value; // 若是有向图，不加，因为有向图可能不是对称图，但是无向图一定是
            }
        }
    }
}

void Dijisktra(MGroup* G, int v0, Para* P, Short* D)
{
    bool final[size];//定义标志，来表示是否找到最小值
    int  k=0;//记录最小下标
    //初始化
    for (int i = 0; i < G->numvex; i++)
    {
        final[i] = false;
        (*D)[i] = G->arc[v0][i];
        (*P)[i] = -1;//-1来表示没有找到最小值
    }
    (*D)[v0] = 0;
    (*P)[v0] = 0;
    final[v0] = true;
    //Dijkstra算法的最短路刷新，判断，记录都和Prime大体相同，我总结为以下几点
    /*
   -- 1 第一次遍历每一个值（这一个值是指的是最短路径长度的那个数组，此题是（D*）数组）
   -- 2 遍历的过程中需要观察是否已经找到了最短路,用final数组表示
   -- 3 第二次遍历，基于第一次遍历的最短路顶点，从该顶点出发，然后与该顶点相连的路径相连，然后与目前最短路进行比较（*D）数组中对应的值 
    
    */
    for (int i = 0; i < G->numvex; i++)
    {
        int min = max;
        for (int j = 0; j < G->numvex; j++)
        {
            if ((*D)[j] < min && !final[j])//判断最小值并且没有找到最值过
            {
                min = (*D)[j];
                k = j;
            }
        }
        final[k] = true;//标志已找到最小值
        for (int j = 0; j < G->numvex; j++)
        {
            if (G->arc[k][j] + min < (*D)[j] && !final[j])//判断从刚刚出去的点是否能找到最小值
            {
                (*D)[j] = G->arc[k][j] + min;
                (*P)[j] = k;
            }
        }
    }
}