数据结构实验6：最短路径算法 6-1 迪杰斯特拉最短路径算法

一张地图包括n个城市，假设城市间由m跳路径（有向图），每条路径的长度已知，给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到重点之间的最短路径。

函数接口定义：

在这里描述结构体和函数接口：
#include <iostream>
using namespace std;
#define ERROR 0
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
int *D=new int[MVNum]; //用于记录最短路的长度
bool *S=new bool[MVNum]; //标记顶点是否进入 S 集合
int *Path=new int[MVNum]; //用于记录最短路顶点的前驱
//图
typedef struct
{
    VerTexType vexs[MVNum];     //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum,arcnum;          //网的当前点数和边数
} AMGraph;
//显示从起点到终点的最短路径
void DisplayPath(AMGraph G, int begin,int end );
int LocateVex(AMGraph G, VerTexType v);
//创建有向网的邻接矩阵
void CreateUDN(AMGraph &G);
//显示图的邻接矩阵
void DisplayG(AMGraph G);
//计算从v0起点的最短路径
void ShortestPath_DJI(AMGraph G,int v0);

裁判测试程序样例：

在这里给出函数被调用进行测试的例子，mode控制测试的不同函数：
int main()
{
    AMGraph G;
    VerTexType start,destination;
    int mode;
    cin>>mode;
    CreateUDN(G);
    int num_start,num_destination;
    cin >> start >> destination;
    //计算起点与终点编号
    num_start = LocateVex(G, start);
    num_destination = LocateVex(G, destination);
    ShortestPath_DJI(G,num_start);//调用函数求最短路径
    switch(mode)
    {
        case 1: DisplayG(G);break;
        case 2: cout<<num_start<<" "<<num_destination<<endl;
                break;
        case 3: cout<<start<<"->"<<destination<<" length:"<<D[num_destination]<<endl;
                break;
        case 4: cout<<start<<"->"<<destination<<endl;
                cout <<"Shortest Path:";
                DisplayPath(G, num_start, num_destination);
                cout << G.vexs[num_destination]<<endl;
    }
    return 0;
}



/* 请在这里填写答案 */

输入样例1：
在这里给出一组输入，第一行是mode的值，代表测试的不同函数，第二行是两个整数n和m，分别代表城市个数和路径条数，第三行有n个字符，代表城市的名称。接着是m行的数据，每一行有两个字符a和b以及一个整数d，代表从城市a到城市b有一条距离为d的路，最后一行为两个字符，代表待求最短路径得城市起点和终点。

1
3 3
A B C
A B 1
B C 1
C A 3
A C
输出样例1：
在这里给出相应的输出，当mode为1，显示创建好的邻接矩阵，不可达的无穷大值显示为字符'∞'（程序中可拷贝本字符），其余显示为有效值，数据之间用逗号分隔。当mode为4，显示从起点到终点的最短路径，城市时间用箭头相隔；其余mode为2，3的显示见测试程序：

∞,1,∞
∞,∞,1
3,∞,∞
输入样例2：
在这里给出一组输入，第一行是mode的值，代表测试的不同函数，第二行是两个整数n和m，分别代表城市个数和路径条数，第三行有n个字符，代表城市的名称。接着是m行的数据，每一行有两个字符a和b以及一个整数d，代表从城市a到城市b有一条距离为d的路，最后一行为两个字符，代表待求最短路径得城市起点和终点。

4
3 3
A B C
A B 1
B C 1
C A 3
A C
输出样例2：
在这里给出相应的输出，当mode为1，显示创建好的邻接矩阵，不可达的无穷大值显示为字符'∞'（程序中可拷贝本字符），其余显示为有效值，数据之间用逗号分隔。当mode为4，显示从起点到终点的最短路径，城市时间用箭头相隔；其余mode为2，3的显示见测试程序：

A->C
Shortest Path:A->B->C

我的答案

int LocateVex(AMGraph G, VerTexType v){
    int i;
    for(i=0;i<G.vexnum;i++){
        if(v==G.vexs[i])return i;
    }return -1;
}
void CreateUDN(AMGraph &G){
     VerTexType v1,v2;
    ArcType w;
    int i,j,k;
    cin>>G.vexnum>>G.arcnum;
    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);
        G.arcs[i][j]=w;
    }
}
void DisplayG(AMGraph G){
    int j,k;
    for(j=0;j<G.vexnum;j++)
         for(k=0;k<G.vexnum;k++){
           if(k!=G.vexnum-1){
             if(G.arcs[j][k]!=MaxInt)
               cout<<G.arcs[j][k]<<",";  
               else cout<<"∞"<<",";
           }
            else{
                if(G.arcs[j][k]!=MaxInt)
                    cout<<G.arcs[j][k]<<endl;
                else cout<<"∞"<<endl;
            }
         }
}
void ShortestPath_DJI(AMGraph G,int v0){
    int v=0;
    int n=G.vexnum;
    int min,i,w;
    for(v;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=0;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[w]+G.arcs[v][w]<D[w])){
                    D[w]=D[v]+G.arcs[v][w];
                    Path[w]=v;
                }//if  
    }
}
void DisplayPath(AMGraph G , int begin ,int end ){
    if(Path[end] != -1){
        DisplayPath(G , begin ,Path[end]);
        cout << G.vexs[Path[end]] << "->";
    }
}

最后一个函数一直错误，但是我看不出来，希望可以指教一下，或者有代码参考一下

最后那里是 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w]))

百度搜“C源代码 迪杰斯特拉算法”

https://blog.csdn.net/weixin_43598687/article/details/123726816

我没有使用递归

int LocateVex(AMGraph G, VerTexType v)
{
    for (int i = 0; i < G.vexnum; i++)
        if (v == G.vexs[i])
            return i;
}
void CreateUDN(AMGraph& G)
{
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++)
        cin >> G.vexs[i];
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;
    for (int i = 0; i < G.arcnum; i++)
    {
        char a, b;
        int w;
        cin >> a >> b >> w;
        G.arcs[LocateVex(G, a)][LocateVex(G, b)] = w;
    }
}
void DisplayG(AMGraph G)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        for (int j = 0; j < G.vexnum; j++)
        {
            if (j != G.vexnum - 1)
            {
                if (G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] << ",";
                else
                    cout << "∞,";
            }
            else
                if (G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] ;
                else
                    cout << "∞";
        }
        cout << endl;
    }
}
void DisplayPath(AMGraph G, int begin, int end)
{
    int arr[MVNum];
    int count=0;
    while(Path[end]!=begin)
    {
        arr[count]=Path[end];
        end=Path[end];
        count++;
    }
    cout<<G.vexs[begin]<<"->";
    for(int i=count-1;i>=0;i--)
    {
        cout<<G.vexs[arr[i]]<<"->";
    }
    
}
void ShortestPath_DJI(AMGraph G, int v0)
{
    for(int i=0;i<G.vexnum;i++)
        D[i]=MaxInt;
    for(int i=0;i<G.vexnum;i++)
        S[i]=false; 
    for(int i=0;i<G.vexnum;i++)
        Path[i]=0;
    for(int i=0;i<G.vexnum;i++)
    {
        D[i]=G.arcs[v0][i];
        if(D[i]!=MaxInt)
            Path[i]=v0;
    }
    D[v0]=0,S[v0]=true,Path[v0]=v0;
    int last=v0;
    for(int i=0;i<G.vexnum-1;i++)
    {
        int min=MaxInt,temp=0;
        for(int j=0;j<G.vexnum;j++)
        {
            if(D[j]<min&&!S[j])
            {
                min=D[j];
                temp=j;
            }
        }
        S[temp]=true;
        for(int j=0;j<G.vexnum;j++)
        {
            if(!S[j]&&D[j]>D[temp]+G.arcs[temp][j])
            {
                D[j]=D[temp]+G.arcs[temp][j];
                Path[j]=temp;
            }
        }
    }
}

一.最短路径
从某顶点（源点）出发到另一顶点（目的地）的路径中，有一条各边（或弧）权值之和最小的路径称为最短路径
迪杰斯特拉算法：从单原点到其余各店的最短路径
二.基本思想
依最短路径的长度递增的次序求得各条路径。其中，从源点到顶点v的最短路径是所有最短路径中长度最短者

路径长度最短的最短路径的特点：
在这条路上，必定只含一条弧，并且这条弧的权值最小（记为v0->v1)
下一条路径长度次短的最短路径的特点：
或者是直接从源点到该点（只含一条弧）
或者是从源点经过顶点v1，再到达该顶点（由两条弧组成）（v0->v1->v2)
再下一条路径长度次短的的最短路径的特点：
或者是直接从源点到该点（只含一条弧）
或者是从源点经过顶点v1，再到达该顶点(由两条弧）
或者是从源点经过顶点v2，再到达该顶点（看v2的情况，第一种就两条弧，第二种就三条弧）

    /*
 * Dijkstra最短路径。
 * 即，统计图(G)中"顶点vs"到其它各个顶点的最短路径。
 *
 * 参数说明：
 *        G -- 图
 *       vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
 *     prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
 *     dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
 */
void dijkstra(Graph G, int vs, int prev[], int dist[])
{
    int i,j,k;
    int min;
    int tmp;
    int flag[MAX];      // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
 
    // 初始化
    for (i = 0; i < G.vexnum; i++)
    {
        flag[i] = 0;              // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }
 
    // 对"顶点vs"自身进行初始化
    flag[vs] = 1;
    dist[vs] = 0;
 
    // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
    for (i = 1; i < G.vexnum; i++)
    {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
        min = INF;
        for (j = 0; j < G.vexnum; j++)
        {
            if (flag[j]==0 && dist[j]<min)
            {
                min = dist[j];
                k = j;
            }
        }
        // 标记"顶点k"为已经获取到最短路径
        flag[k] = 1;
 
        // 修正当前最短路径和前驱顶点
        // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
        for (j = 0; j < G.vexnum; j++)
        {
            tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
            if (flag[j] == 0 && (tmp  < dist[j]) )
            {
                dist[j] = tmp;
                prev[j] = k;
            }
        }
    }
 
    // 打印dijkstra最短路径的结果
    printf("dijkstra(%c): \n", G.vexs[vs]);
    for (i = 0; i < G.vexnum; i++)
        printf("  shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);
}