迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 Dijkstra算法基本思想通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。Dijkstra算法操作步骤初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。重复步骤(2)和(3)，直到遍历完所有顶点。单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。<img src="/upload/content/20200515/1589556359708699.jpg" alt="Dijkstra算法（迪杰斯特拉算法）详解"title="Dijkstra算法（迪杰斯特拉算法）详解" width="550px">以上图G4为例，来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)。以下B节点中23应为13。<img src="/upload/content/20200515/1589556377160612.jpg" alt="Dijkstra算法（迪杰斯特拉算法）详解"title="Dijkstra算法（迪杰斯特拉算法）详解" width="550px">初始状态：S是已计算出最短路径的顶点集合，U是未计算除最短路径的顶点的集合！第1步：将顶点D加入到S中。此时，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)表示C到起点D的距离是3。第2步：将顶点C加入到S中。上一步操作之后，U中顶点C到起点D的距离最短；因此，将C加入到S中，同时更新U中顶点的距离。以顶点F为例，之前F到D的距离为∞；但是将C加入到S之后，F到D的距离为9=(F,C)+(C,D)。此时，S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。第3步：将顶点E加入到S中。上一步操作之后，U中顶点E到起点D的距离最短；因此，将E加入到S中，同时更新U中顶点的距离。还是以顶点F为例，之前F到D的距离为9；但是将E加入到S之后，F到D的距离为6=(F,E)+(E,D)。此时，S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。第4步：将顶点F加入到S中。此时，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。第5步：将顶点G加入到S中。此时，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。第6步：将顶点B加入到S中。此时，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。第7步：将顶点A加入到S中。此时，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。此时，起点D到各个顶点的最短距离就计算出来了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。Dijkstra算法代码邻接矩阵为例，<pre class="brush:cpp;toolbar:false">//&nbsp;邻接矩阵
typedef&nbsp;struct&nbsp;_graph
{
&nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;vexs[MAX];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;顶点集合
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;vexnum;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;顶点数
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;edgnum;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;边数
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;matrix[MAX][MAX];&nbsp;//&nbsp;邻接矩阵
}Graph,&nbsp;*PGraph;
//&nbsp;边的结构体
typedef&nbsp;struct&nbsp;_EdgeData
{
&nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;start;&nbsp;//&nbsp;边的起点
&nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;end;&nbsp;&nbsp;&nbsp;//&nbsp;边的终点
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;weight;&nbsp;//&nbsp;边的权重
}EData;</pre>Graph是邻接矩阵对应的结构体。vexs用于保存顶点，vexnum是顶点数，edgnum是边数；matrix则是用于保存矩阵信息的二维数组。例如，matrix[i][j]=1，则表示”顶点i(即vexs[i])”和”顶点j(即vexs[j])”是邻接点；matrix[i][j]=0，则表示它们不是邻接点。EData是邻接矩阵边对应的结构体。Dijkstra算法<pre class="brush:cpp;toolbar:false">/*
&nbsp;*&nbsp;Dijkstra最短路径。
&nbsp;*&nbsp;即，统计图(G)中&quot;顶点vs&quot;到其它各个顶点的最短路径。
&nbsp;*
&nbsp;*&nbsp;参数说明：
&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;G&nbsp;--&nbsp;图
&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vs&nbsp;--&nbsp;起始顶点(start&nbsp;vertex)。即计算&quot;顶点vs&quot;到其它顶点的最短路径。
&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev&nbsp;--&nbsp;前驱顶点数组。即，prev[i]的值是&quot;顶点vs&quot;到&quot;顶点i&quot;的最短路径所经历的全部顶点中，位于&quot;顶点i&quot;之前的那个顶点。
&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist&nbsp;--&nbsp;长度数组。即，dist[i]是&quot;顶点vs&quot;到&quot;顶点i&quot;的最短路径的长度。
&nbsp;*/
void&nbsp;dijkstra(Graph&nbsp;G,&nbsp;int&nbsp;vs,&nbsp;int&nbsp;prev[],&nbsp;int&nbsp;dist[])
{
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,j,k;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;min;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;tmp;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;flag[MAX];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;flag[i]=1表示&quot;顶点vs&quot;到&quot;顶点i&quot;的最短路径已成功获取。
&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;初始化
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;G.vexnum;&nbsp;i++)
&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag[i]&nbsp;=&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;顶点i的最短路径还没获取到。
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev[i]&nbsp;=&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;顶点i的前驱顶点为0。
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[i]&nbsp;=&nbsp;G.matrix[vs][i];//&nbsp;顶点i的最短路径为&quot;顶点vs&quot;到&quot;顶点i&quot;的权。
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;对&quot;顶点vs&quot;自身进行初始化
&nbsp;&nbsp;&nbsp;&nbsp;flag[vs]&nbsp;=&nbsp;1;
&nbsp;&nbsp;&nbsp;&nbsp;dist[vs]&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;遍历G.vexnum-1次；每次找出一个顶点的最短路径。
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;1;&nbsp;i&nbsp;&lt;&nbsp;G.vexnum;&nbsp;i++)
&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;寻找当前最小的路径；
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;min&nbsp;=&nbsp;INF;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j&nbsp;=&nbsp;0;&nbsp;j&nbsp;&lt;&nbsp;G.vexnum;&nbsp;j++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(flag[j]==0&nbsp;&amp;&amp;&nbsp;dist[j]&lt;min)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;min&nbsp;=&nbsp;dist[j];
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;=&nbsp;j;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;标记&quot;顶点k&quot;为已经获取到最短路径
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag[k]&nbsp;=&nbsp;1;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;修正当前最短路径和前驱顶点
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;即，当已经&quot;顶点k的最短路径&quot;之后，更新&quot;未获取最短路径的顶点的最短路径和前驱顶点&quot;。
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j&nbsp;=&nbsp;0;&nbsp;j&nbsp;&lt;&nbsp;G.vexnum;&nbsp;j++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp&nbsp;=&nbsp;(G.matrix[k][j]==INF&nbsp;?&nbsp;INF&nbsp;:&nbsp;(min&nbsp;+&nbsp;G.matrix[k][j]));&nbsp;//&nbsp;防止溢出
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(flag[j]&nbsp;==&nbsp;0&nbsp;&amp;&amp;&nbsp;(tmp&nbsp;&nbsp;&lt;&nbsp;dist[j])&nbsp;)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[j]&nbsp;=&nbsp;tmp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev[j]&nbsp;=&nbsp;k;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;打印dijkstra最短路径的结果
&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;dijkstra(%c):&nbsp;\n&quot;,&nbsp;G.vexs[vs]);
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;G.vexnum;&nbsp;i++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;&nbsp;&nbsp;shortest(%c,&nbsp;%c)=%d\n&quot;,&nbsp;G.vexs[vs],&nbsp;G.vexs[i],&nbsp;dist[i]);
}</pre>Dijkstra算法的代码实现（c++）Dijkstra.h文件的代码<pre class="brush:cpp;toolbar:false">/************************************************************/
/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;程序作者：Willam&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/
/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;程序完成时间：2017/3/8&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/
/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;有任何问题请联系：2930526477@qq.com&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/
/************************************************************/
#pragma&nbsp;once
//#pragma&nbsp;once是一个比较常用的C/C++杂注，
//只要在头文件的最开始加入这条杂注，
//就能够保证头文件只被编译一次。
#include&lt;iostream&gt;
#include&lt;string&gt;
using&nbsp;namespace&nbsp;std;
/*
本程序是使用Dijkstra算法实现求解最短路径的问题
采用的邻接矩阵来存储图
*/
//记录起点到每个顶点的最短路径的信息
struct&nbsp;Dis&nbsp;
{
&nbsp;&nbsp;&nbsp;&nbsp;string&nbsp;path;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;value;
&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;visit;
&nbsp;&nbsp;&nbsp;&nbsp;Dis()&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visit&nbsp;=&nbsp;false;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;value&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;path&nbsp;=&nbsp;&quot;&quot;;
&nbsp;&nbsp;&nbsp;&nbsp;}
};
class&nbsp;Graph_DG&nbsp;
{
private:
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;vexnum;&nbsp;&nbsp;&nbsp;//图的顶点个数
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;edge;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//图的边数
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;**arc;&nbsp;&nbsp;&nbsp;//邻接矩阵
&nbsp;&nbsp;&nbsp;&nbsp;Dis&nbsp;*&nbsp;dis;&nbsp;&nbsp;&nbsp;//记录各个顶点最短路径的信息
public:
&nbsp;&nbsp;&nbsp;&nbsp;//构造函数
&nbsp;&nbsp;&nbsp;&nbsp;Graph_DG(int&nbsp;vexnum,&nbsp;int&nbsp;edge);
&nbsp;&nbsp;&nbsp;&nbsp;//析构函数
&nbsp;&nbsp;&nbsp;&nbsp;~Graph_DG();
&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;判断我们每次输入的的边的信息是否合法
&nbsp;&nbsp;&nbsp;&nbsp;//顶点从1开始编号
&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;check_edge_value(int&nbsp;start,&nbsp;int&nbsp;end,&nbsp;int&nbsp;weight);
&nbsp;&nbsp;&nbsp;&nbsp;//创建图
&nbsp;&nbsp;&nbsp;&nbsp;void&nbsp;createGraph();
&nbsp;&nbsp;&nbsp;&nbsp;//打印邻接矩阵
&nbsp;&nbsp;&nbsp;&nbsp;void&nbsp;print();
&nbsp;&nbsp;&nbsp;&nbsp;//求最短路径
&nbsp;&nbsp;&nbsp;&nbsp;void&nbsp;Dijkstra(int&nbsp;begin);
&nbsp;&nbsp;&nbsp;&nbsp;//打印最短路径
&nbsp;&nbsp;&nbsp;&nbsp;void&nbsp;print_path(int);
};</pre>Dijkstra.cpp文件的代码<pre class="brush:cpp;toolbar:false">#include&quot;Dijkstra.h&quot;
//构造函数
Graph_DG::Graph_DG(int&nbsp;vexnum,&nbsp;int&nbsp;edge)&nbsp;
{
&nbsp;&nbsp;&nbsp;&nbsp;//初始化顶点数和边数
&nbsp;&nbsp;&nbsp;&nbsp;this-&gt;vexnum&nbsp;=&nbsp;vexnum;
&nbsp;&nbsp;&nbsp;&nbsp;this-&gt;edge&nbsp;=&nbsp;edge;
&nbsp;&nbsp;&nbsp;&nbsp;//为邻接矩阵开辟空间和赋初值
&nbsp;&nbsp;&nbsp;&nbsp;arc&nbsp;=&nbsp;new&nbsp;int*[this-&gt;vexnum];
&nbsp;&nbsp;&nbsp;&nbsp;dis&nbsp;=&nbsp;new&nbsp;Dis[this-&gt;vexnum];
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;this-&gt;vexnum;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arc[i]&nbsp;=&nbsp;new&nbsp;int[this-&gt;vexnum];
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;k&nbsp;=&nbsp;0;&nbsp;k&nbsp;&lt;&nbsp;this-&gt;vexnum;&nbsp;k++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//邻接矩阵初始化为无穷大
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arc[i][k]&nbsp;=&nbsp;INT_MAX;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
}
//析构函数
Graph_DG::~Graph_DG()&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;delete[]&nbsp;dis;
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;this-&gt;vexnum;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;delete&nbsp;this-&gt;arc[i];
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;delete&nbsp;arc;
}
//&nbsp;判断我们每次输入的的边的信息是否合法
//顶点从1开始编号
bool&nbsp;Graph_DG::check_edge_value(int&nbsp;start,&nbsp;int&nbsp;end,&nbsp;int&nbsp;weight)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(start&lt;1&nbsp;||&nbsp;end&lt;1&nbsp;||&nbsp;start&gt;vexnum&nbsp;||&nbsp;end&gt;vexnum&nbsp;||&nbsp;weight&nbsp;&lt;&nbsp;0)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;
}
void&nbsp;Graph_DG::createGraph()&nbsp;
{
&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;请输入每条边的起点和终点（顶点编号从1开始）以及其权重&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;start;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;end;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;weight;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(count&nbsp;!=&nbsp;this-&gt;edge)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;start&nbsp;&gt;&gt;&nbsp;end&nbsp;&gt;&gt;&nbsp;weight;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//首先判断边的信息是否合法
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(!this-&gt;check_edge_value(start,&nbsp;end,&nbsp;weight))&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;输入的边的信息不合法，请重新输入&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;start&nbsp;&gt;&gt;&nbsp;end&nbsp;&gt;&gt;&nbsp;weight;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//对邻接矩阵对应上的点赋值
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arc[start&nbsp;-&nbsp;1][end&nbsp;-&nbsp;1]&nbsp;=&nbsp;weight;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//无向图添加上这行代码
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//arc[end&nbsp;-&nbsp;1][start&nbsp;-&nbsp;1]&nbsp;=&nbsp;weight;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;++count;
&nbsp;&nbsp;&nbsp;&nbsp;}
}
void&nbsp;Graph_DG::print()&nbsp;
{
&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;图的邻接矩阵为：&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count_row&nbsp;=&nbsp;0;&nbsp;//打印行的标签
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count_col&nbsp;=&nbsp;0;&nbsp;//打印列的标签
&nbsp;&nbsp;&nbsp;&nbsp;//开始打印
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(count_row&nbsp;!=&nbsp;this-&gt;vexnum)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count_col&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(count_col&nbsp;!=&nbsp;this-&gt;vexnum)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(arc[count_row][count_col]&nbsp;==&nbsp;INT_MAX)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;∞&quot;&nbsp;&lt;&lt;&nbsp;&quot;&nbsp;&quot;;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;arc[count_row][count_col]&nbsp;&lt;&lt;&nbsp;&quot;&nbsp;&quot;;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;++count_col;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;++count_row;
&nbsp;&nbsp;&nbsp;&nbsp;}
}
void&nbsp;Graph_DG::Dijkstra(int&nbsp;begin)
{
&nbsp;&nbsp;&nbsp;&nbsp;//首先初始化我们的dis数组
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;this-&gt;vexnum;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//设置当前的路径
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[i].path&nbsp;=&nbsp;&quot;v&quot;&nbsp;+&nbsp;to_string(begin)&nbsp;+&nbsp;&quot;--&gt;v&quot;&nbsp;+&nbsp;to_string(i&nbsp;+&nbsp;1);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[i].value&nbsp;=&nbsp;arc[begin&nbsp;-&nbsp;1][i];
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;//设置起点的到起点的路径为0
&nbsp;&nbsp;&nbsp;&nbsp;dis[begin&nbsp;-&nbsp;1].value&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;dis[begin&nbsp;-&nbsp;1].visit&nbsp;=&nbsp;true;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count&nbsp;=&nbsp;1;
&nbsp;&nbsp;&nbsp;&nbsp;//计算剩余的顶点的最短路径（剩余this-&gt;vexnum-1个顶点）
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(count&nbsp;!=&nbsp;this-&gt;vexnum)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//temp用于保存当前dis数组中最小的那个下标
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//min记录的当前的最小值
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;temp=0;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;min&nbsp;=&nbsp;INT_MAX;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;this-&gt;vexnum;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!dis[i].visit&nbsp;&amp;&amp;&nbsp;dis[i].value&lt;min)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;min&nbsp;=&nbsp;dis[i].value;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp&nbsp;=&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//cout&nbsp;&lt;&lt;&nbsp;temp&nbsp;+&nbsp;1&nbsp;&lt;&lt;&nbsp;&quot;&nbsp;&nbsp;&quot;&lt;&lt;min&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//把temp对应的顶点加入到已经找到的最短路径的集合中
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[temp].visit&nbsp;=&nbsp;true;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;++count;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&lt;&nbsp;this-&gt;vexnum;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//注意这里的条件arc[temp][i]!=INT_MAX必须加，不然会出现溢出，从而造成程序异常
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!dis[i].visit&nbsp;&amp;&amp;&nbsp;arc[temp][i]!=INT_MAX&nbsp;&amp;&amp;&nbsp;(dis[temp].value&nbsp;+&nbsp;arc[temp][i])&nbsp;&lt;&nbsp;dis[i].value)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//如果新得到的边可以影响其他为访问的顶点，那就就更新它的最短路径和长度
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[i].value&nbsp;=&nbsp;dis[temp].value&nbsp;+&nbsp;arc[temp][i];
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[i].path&nbsp;=&nbsp;dis[temp].path&nbsp;+&nbsp;&quot;--&gt;v&quot;&nbsp;+&nbsp;to_string(i&nbsp;+&nbsp;1);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
}
void&nbsp;Graph_DG::print_path(int&nbsp;begin)&nbsp;
{
&nbsp;&nbsp;&nbsp;&nbsp;string&nbsp;str;
&nbsp;&nbsp;&nbsp;&nbsp;str&nbsp;=&nbsp;&quot;v&quot;&nbsp;+&nbsp;to_string(begin);
&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;以&quot;&lt;&lt;str&lt;&lt;&quot;为起点的图的最短路径为：&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;!=&nbsp;this-&gt;vexnum;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(dis[i].value!=INT_MAX)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;dis[i].path&nbsp;&lt;&lt;&nbsp;&quot;=&quot;&nbsp;&lt;&lt;&nbsp;dis[i].value&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;dis[i].path&nbsp;&lt;&lt;&nbsp;&quot;是无最短路径的&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
}</pre>main.cpp文件的代码<pre class="brush:cpp;toolbar:false">#include&quot;Dijkstra.h&quot;
//检验输入边数和顶点数的值是否有效，可以自己推算为啥：
//顶点数和边数的关系是：((Vexnum*(Vexnum&nbsp;-&nbsp;1))&nbsp;/&nbsp;2)&nbsp;&lt;&nbsp;edge
bool&nbsp;check(int&nbsp;Vexnum,&nbsp;int&nbsp;edge)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(Vexnum&nbsp;&lt;=&nbsp;0&nbsp;||&nbsp;edge&nbsp;&lt;=&nbsp;0&nbsp;||&nbsp;((Vexnum*(Vexnum&nbsp;-&nbsp;1))&nbsp;/&nbsp;2)&nbsp;&lt;&nbsp;edge)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false;
&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;
}
int&nbsp;main()&nbsp;
{
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;vexnum;&nbsp;int&nbsp;edge;
&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;输入图的顶点个数和边的条数：&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;vexnum&nbsp;&gt;&gt;&nbsp;edge;
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(!check(vexnum,&nbsp;edge))&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;&quot;输入的数值不合法，请重新输入&quot;&nbsp;&lt;&lt;&nbsp;endl;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;vexnum&nbsp;&gt;&gt;&nbsp;edge;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;Graph_DG&nbsp;graph(vexnum,&nbsp;edge);
&nbsp;&nbsp;&nbsp;&nbsp;graph.createGraph();
&nbsp;&nbsp;&nbsp;&nbsp;graph.print();
&nbsp;&nbsp;&nbsp;&nbsp;graph.Dijkstra(1);
&nbsp;&nbsp;&nbsp;&nbsp;graph.print_path(1);
&nbsp;&nbsp;&nbsp;&nbsp;system(&quot;pause&quot;);
&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;
}</pre>输入：<pre class="brush:bash;toolbar:false">6&nbsp;8
1&nbsp;3&nbsp;10
1&nbsp;5&nbsp;30
1&nbsp;6&nbsp;100
2&nbsp;3&nbsp;5
3&nbsp;4&nbsp;50
4&nbsp;6&nbsp;10
5&nbsp;6&nbsp;60
5&nbsp;4&nbsp;20</pre>从输出可以看出，程序的结果和我们之前手动计算的结果是一样的。<img src="/upload/content/20200515/1589556961496651.jpg" alt="Dijkstra算法（迪杰斯特拉算法）详解"title="Dijkstra算法（迪杰斯特拉算法）详解" width="550px">

Dijkstra算法（迪杰斯特拉算法）详解

From 博客园

Still Have Questions?