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

掌握迪杰斯特拉方法

设计文档

 代码

#include<iostream>
using namespace std;
//迪杰特斯拉：邻接矩阵：一维数组+二维数组+点边数
typedef int VexType;
#define MVNum 100
#define MaxInt 32767
int S[MVNum],Path[MVNum],D[MVNum];//迪杰特斯拉的三个数组
typedef struct{
    VexType vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G,VexType v)
{
    for(int i=0;i<G.vexnum;++i)
        if(G.vexs[i]==v)return i;
    return -1;
}
void CreatAMGraph(AMGraph &G,int &err)
{
    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 k=0;k<G.arcnum;++k)
    {
        VexType v1,v2;
        int w;
        cin>>v1>>v2>>w;
        int i=LocateVex(G,v1),j=LocateVex(G,v2);
        if(i==-1||j==-1)    err=1;
        else    G.arcs[i][j]=w;//有向网，只用一次
    }
}
void ShortestPath_DIJ(AMGraph G,int vo)
{
    for(int v=0;v<G.vexnum;++v)//这里出的问题
    {
        S[v]=0;
        D[v]=G.arcs[vo][v];
        if(D[v]<MaxInt)Path[v]=vo;
        else Path[v]=-1;
    }
    S[vo]=1;D[vo]=0;
//     for(int i=0;i<G.vexnum;++i){
//         if(G.arcs[vo][i]!=MaxInt)//说明i与vo有边的关系
//         {
//             D[i]=G.arcs[vo][i];
//             Path[i]=vo;
//         }
//     }
    for(int k=0;k<G.vexnum-1;++k)//对剩下的n-1个顶点进行计算
    {
        int wmin=MaxInt,vmin;//找权值最小和其下标
        for(int w=0;w<G.vexnum;++w){//找权值最小的，纳入S中
            if(!S[w]&&D[w]<wmin){
                vmin=w;wmin=D[w];
            }
        }
        S[vmin]=1;
        for(int i=0;i<G.vexnum;++i){
            if(!S[i]&&(D[vmin]+G.arcs[vmin][i]<D[i]))
            {
                D[i]=D[vmin]+G.arcs[vmin][i];
                Path[i]=vmin;
            }
        }
    }
}
int main()
{
    AMGraph G;
    int err=0;
    VexType vo,ve;
    CreatAMGraph(G,err);//err的值为1的时候说明在创建邻接矩阵的时候出现了错误
    cin>>vo>>ve;
    int i=LocateVex(G,vo),j=LocateVex(G,ve);
    if(i!=-1&&j!=-1){
        ShortestPath_DIJ(G,i);
        int adj[MVNum],k=1;
        adj[0]=j;
        while(Path[j]!=i)
        {
            adj[k]=Path[j];
            j=Path[j];
            ++k;
        }
        adj[k]=i;
        for(int n=k;n>=0;--n){
            if(n!=0)cout<<G.vexs[adj[n]]<<"-->";
            else cout<<G.vexs[adj[n]];
        }
    }
    return 0;
}

1.实验中遇到的具体问题
1）如何正确地初始化距离和路径信息？

2）如何有效地选取未访问过的顶点中具有最小距离的顶点？

3）如何更新已访问顶点的相邻顶点的距离？

2.问题如何解决的
初始化距离和路径信息：在开始时，将所有顶点的距离设置为无穷大（除了起始顶点，其距离设置为0），并标记所有顶点为未访问。路径信息可以用一个数组来存储，初始时每个顶点的路径设置为空或起始顶点。

选取未访问过的顶点中具有最小距离的顶点：可以使用一个优先队列来实现。优先队列中的元素按照距离进行排序，每次从队列中取出距离最小的顶点进行处理。处理完一个顶点后，更新其相邻顶点的距离，并将更新后的顶点加入优先队列。

更新已访问顶点的相邻顶点的距离：当访问一个顶点时，遍历其所有邻居。如果通过当前顶点到达某个邻居的距离小于该邻居当前的距离，则更新该邻居的距离，并将其路径设置为通过当前顶点到达。

3.实验设计思路

定义了一个结构体 AMGraph 来表示图，其中包含顶点数组 vexs 和邻接矩阵 arcs。邻接矩阵是一个二维数组，其中 arcs[i][j] 表示从顶点 i 到顶点 j 的边的权值。如果 i 和 j 之间没有边，则用 MaxInt 来初始化。

主要函数包括：

LocateVex：这个函数用于在图 G 中查找顶点 v 的索引。如果找到，返回索引；如果没找到，返回 -1。

CreatAMGraph：这个函数用于创建图 G。它首先从输入中读取顶点数和边数，然后读取每个顶点的名字，并将它们存储在 vexs 数组中。然后，它初始化邻接矩阵 arcs 为 MaxInt。最后，它从输入中读取每条边的两个顶点以及它们的权值，并更新邻接矩阵 arcs。如果在读取边的过程中出现错误（例如，某个顶点不在 vexs 数组中），则将 err 设置为 1。

ShortestPath_DIJ：这个函数实现了迪杰斯特拉算法。首先，对于每个顶点 v，设置 S[v] 为 0，D[v] 为从 vo 到 v 的权值（如果存在路径），Path[v] 为 vo（如果存在路径）。然后，对于每个顶点 v，如果它与 vo 之间存在边，则更新 D[v] 和 Path[v]。重复这个过程直到所有的顶点都被处理。

在 main 函数中，首先创建图 G，然后从输入中读取起始点和终点，然后使用迪杰斯特拉算法查找这两个点之间的最短路径。

这个实验的设计思路是使用邻接矩阵来表示图，并实现迪杰斯特拉算法来查找最短路径。这个算法基于贪心策略，每次找到距离起始点最近的顶点，然后更新通过这个顶点的所有边的权值。这个过程重复进行，直到所有的顶点都被处理。

4.实验后的感想
在完成这个实验后，我对图的邻接矩阵表示和迪杰斯特拉算法有了更深入的理解。邻接矩阵是一种常见的图的表示方法，它使用一个二维数组来表示顶点之间的关系。迪杰斯特拉算法是一种用于寻找图中两点间最短路径的算法。