迪杰斯特拉方法实现最短路径2021/11/26

迪杰斯特拉方法实现最短路径

输入格式:

第一行输入有向网的顶点和边数，第二行输入各顶点值，用空格间隔，第三行开始输入各条边的 两个点的及边上的权值，用空格间隔。最后一行输入要求路径的两个顶点。

输出格式:

输出最短路径经过的各顶点，中间用-->连接。

输入样例:

在这里给出一组输入。例如：

6 8
0 1 2 3 4 5
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0 3

输出样例:

在这里给出相应的输出。例如：

0-->4-->3

#include 
#include 
#include <string>
#include 
#include 
using namespace std;
#define MAX_VERTEX_NUM 20
struct Graph {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    string vexs[MAX_VERTEX_NUM];
    int vexnum, arcnum;
};
int LocateVex(Graph G, string v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}
void CreateGraph(Graph *G) {
    //cout << "请输入顶点数和弧数: " << endl;
    cin >> G->vexnum >> G->arcnum;
    //cout << "请输入顶点: " << endl;
    for (int i = 0; i < G->vexnum; i++) {
        cin >> G->vexs[i];
        G->arcs[i][i] = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            if (i != j) {
                G->arcs[i][j] = INT_MAX;
            }
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        //cout << "请输入边的两个顶点, from v1 to v2: " << endl;
        string v1, v2;
        cin >> v1 >> v2;
        int i1 = LocateVex(*G, v1);
        int i2 = LocateVex(*G, v2);
        //cout << "请输入弧的权值: " << endl;
        cin >> G->arcs[i1][i2];
    }
}
int ShortestPath_DIJ(Graph G) {
    //cout << "请输入想查询到其他点最短距离的起点: " << endl;
    string s0;
    string s1;
    cin >> s0;
    cin >> s1;

    int v0 = LocateVex(G, s0);
    int v1 = LocateVex(G, s1);

    const int num = G.vexnum;
    int flag_1=0;
    int flag_2=0;
    /*for (int i = 0; i < num; i++)
    {

        //cout<*/
    vector<int> path[num];
    int ShortPathTable[num];
    bool final[num];
    for (int i = 0; i < G.vexnum; i++) {
        final[i] = false;
        ShortPathTable[i] = G.arcs[v0][i];
        if (ShortPathTable[i] < INT_MAX) {
            path[i].push_back(v0);
            path[i].push_back(i);
        }
    }
    ShortPathTable[v0] = 0;
    final[v0] = true;
    for (int i = 1; i < G.vexnum; i++) {
        int min = INT_MAX;
        int v = 0;
        for (int w = 0; w < G.vexnum; w++) {
            if (!final[w]) {
                if (ShortPathTable[w] < min) {
                    min = ShortPathTable[w];
                    v = w;
                }
            }
        }
        final[v] = true;
        for (int w = 0; w < G.vexnum; w++) {
            if (!final[w] && G.arcs[v][w] < INT_MAX && min + G.arcs[v][w] < ShortPathTable[w]) {
                ShortPathTable[w] = min + G.arcs[v][w];
                path[w].clear();
                path[w] = path[v];
                path[w].push_back(w);
            }
        }
    }
    //for (int i = 0; i < num; i++)
     {
         int i=v1;
        if (i != v0) {
                // cout<<1<
            if (ShortPathTable[i] == INT_MAX) {
                cout << "从源点" << G.vexs[v0] << "到终点" << G.vexs[i] << "不可达！" << endl;
            }
            else {

                //cout << "从源点" << G.vexs[v0] << "到终点" << G.vexs[i] << "的最短路径: " << endl;
                cout << G.vexs[path[i][0]];
                for (int j = 1; j < path[i].size(); j++) {
                   // if(j==v1)
                    cout << "-->" << G.vexs[path[i][j]];
                }
                cout << endl;
                //cout << "其最短长度为: " << endl;
                //cout << ShortPathTable[i] << endl;
            }
            //cout << "----------------------------------" << endl;
        }
    }
    return 1;
}
int main () {
    Graph G;
    CreateGraph(&G);
    ShortestPath_DIJ(G);
    return 0;
}