Dijkstra(迪杰特斯拉）算法（极简版）

示例：用Dijkstra算法求A到图中各点的最短路径

Dijkstral算法伪代码如下：

            n次循环至n个顶点全部遍历：

                        1.1从权值数组中找到权值最小的，标记该边端点k

                        1.2打印该路径及权值

                        2.1如果存在经过顶点k到顶点i的边比v->i的权值小

                        2.2更新权值数组及对应路径

源码：

#include<iostream>
#include<iomanip>//控制格式
#include<string>


#define INF 0x3f3f3f3f//定义无穷大
using namespace std;


#define vertexNum 5//源点数
int G[vertexNum][vertexNum];//邻接矩阵
string vertex[]={"A","B","C","D","E"};//源点字符串组
void CreateMGraph()
{
    for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
    {
        G[i][j]=INF;
    }
    G[0][1]=10;G[0][3]=30;G[0][4]=100;
    G[1][2]=50;
    G[2][4]=10;
    G[3][2]=20;G[3][4]=60;
}
void Dijkstra(int v)
{
    int dist[vertexNum],i,num,k,min;//dist为权值存储数组
    string path[vertexNum];
    int s[vertexNum]={0};//初始化标记数组
    cout<<"初始权值数组和路径字符串数组:"<<endl;
    for(i=0;i<vertexNum;i++)
    {
        dist[i]=G[v][i];
        path[i]=vertex[v]+"-->"+vertex[i];
        cout<<path[i]<<" ";
        if(dist[i]!=INF) cout<<dist[i]<<endl;
        else cout<<"∞"<<endl;
    }
    s[v]=1;//标记第一个访问点
    dist[v]=0;
    num=1;//计数器
    cout<<"打印源点A到各点的最短路径及其权值和："<<endl;
    while(num<=vertexNum)//当不取等号时将不会获得A到自身的路径
    {
        min=INF;
        for(k=0,i=0;i<vertexNum;i++)//查找最小值
            {
            if(s[i]==0&&(dist[i]<min)) {min=dist[i];k=i;}
            }
        cout<<path[k]<<"  "<<dist[k]<<endl;//打印路径及对应路径长（权值和）
        s[k]=1;num++;
        for(i=0;i<vertexNum;i++)//更新权值数组和字符串数组
            if((dist[i]>dist[k]+G[k][i])&&(G[k][i]!=INF))
        {
            dist[i]=dist[k]+G[k][i];
            path[i]=path[k]+"-->"+vertex[i];
        }
    }
}


int main()
{
    CreateMGraph();//创建邻接矩阵
    cout<<"打印邻接矩阵："<<endl;
     for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
    {
        if(G[i][j]==INF) cout<<setw(4)<<"∞";
        else cout<<setw(4)<<G[i][j];
        if(j==vertexNum-1) cout<<endl;
    }
    Dijkstra(0);//以A为源点
    return 0;

}

示例截图：

喜欢记得给个赞哦