【NOIP算法】图论 - Dijkstra算法

概述

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。图论的内容属于较为复杂的算法问题，看了一些博客文章，基本都描述冗长，只好自己来写了。我试图用简洁的语言、清晰的图示 、明确的步骤带你用一个半天精力搞清楚这个问题。

图解：Dijkstra算法的基本思想

以上图G1为例，对对迪杰斯特拉进行算法演示(以第4个顶点D为起点)

引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

第一步：选取顶点D

第二步：选取顶点F

因为在集合U中F距离D最近，更新U中剩余节点距离起始点D的最近距离

第三步：选取顶点E

因为在集合U中F距离D最近，更新U中剩余节点距离起始点D的最近距离（分析对比后发现不需要更新）

第四步：选取顶点C

因为在U中C距离D最近，更新U中剩余节点的值距离起始点D的距离（分析对比后发现不需要更新）

第五步：选取顶点B

因为在U中B距离D最近，更新U中剩余节点的值距离起始点D的距离（分析对比后发现不需要更新）

第六步：选取剩下的顶点A

此时，D到各个顶点的最短距离就计算出来了：A（20）、B（9）、C（8）、D（0）、E（7）、F（6）

代码

一般我们用邻接矩阵来存储图，代码中INF是无穷大的含义。

#include<iostream>
using namespace std;

#define MAX 20
#define INF 0x7f7f7f7f 
typedef struct
{
     char vexs[MAX];  //顶点集合
     int vexnum;   //顶点数
     int edgnum;   //边数
     int matrix[MAX][MAX]; //邻接矩阵，保存矩阵的邻接关系 
}Graph,*PGraph;

void dijkstra(Graph G,int vs,int dist[])
{
     int i,j,k;
     int min,tmp;
     int flag[MAX]; //flag[i]=1表示"顶点vs"到"顶点i"的最短路径已经成功获取
 
     //初始化
     for(i=0;i<G.vexnum;i++)
     {
          flag[i]=0;  //顶点i的最短路径还没有获取到
          dist[i]=G.matrix[vs][i]; //顶点i的最短路径为"顶点vs"到"顶点i"的权 
     }  
     flag[vs]=1;
     dist[vs]=0;
 
     //遍历G.vexnum-1次，每次找出一个顶点的最短路径
     for(i=1;i<G.vexnum;i++)
     {
          min = INF;
          for(j=0;j<G.vexnum;j++)
          {
               if(flag[j]==0&&dist[j]<min)
               {
                    min = dist[j]; //当前新加入的节点距离顶点vs的最小值 
                    k = j;    //k中保存当前距离顶点vs最小的下标 
               } 
          }
          //标记"顶点k"为已经获取到最短路径 
          flag[k]=1;
  
          //修正当前最短路径
          for(j=0;j<G.vexnum;j++)
          {
           //防止溢出 
               tmp = (G.matrix[k][j]==INF?INF:(min + G.matrix[k][j]));   //与新加入的节点直接相连的节点需要更新距离vs的最值 
               if(flag[j]==0&&(tmp<dist[j]))
               {
                    dist[j]=tmp;
               } 
          } 
     } 
 
     cout<<"dijkstra("<<G.vexs[vs]<<")"<<endl;
     for(i=0;i<G.vexnum;i++)
     {  
          cout<<"shortest("<<G.vexs[vs]<<","<<G.vexs[i]<<")="<<dist[i]<<endl;
     } 
}

int main(){
 
 //将无向图用邻接矩阵存储 
 Graph graph={
  {'A','B','C','D','E','F'},  //顶点的集合 
  6,         //顶点数目
  10,         //边的数目
  {{INF,12,16,INF,INF,14},    //邻接矩阵 
   {12,INF,INF,INF,5,3},
   {16,INF,INF,13,INF,2},
   {INF,INF,13,INF,7,6},
   {INF,5,INF,7,INF,9},
   {14,3,2,6,9,INF}}       //无向图 
 };
 
 int dist[6]; 
 int vs=3; 
 dijkstra(graph,vs,dist);    //调用函数 
 return 0;
}

运行结果如下：

dijkstra(D)
shortest(D,A)=20
shortest(D,B)=9
shortest(D,C)=8
shortest(D,D)=0
shortest(D,E)=7
shortest(D,F)=6

写得还不够细致，有空会持续更新，争取更加简明、清晰、易懂～

—<完>—