迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法，是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩散，直到扩展到终点为止。
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int edgs;
int points;
int dis[20];
int flag[20];
int infinity=9999999;
cin>>points>>edgs;
int edg[20][20];
for(int i=1;i<=points;i++)
{
for(int j=1;j<=points;j++)
{
if(i==j)
{
edg[i][j]=___(1)_____;
}
else
{
edg[i][j]=_____(2)____;
}
}
}
int point1,point2,quanzhi;
for(int i=1;i<=edgs;i++)
{
cin>>point1>>point2>>quanzhi;
edg[point1][point2]=_____(3)_____;
}
for(int i=1;i<=points;i++)
{
dis[i]=edg[1][i];
}
for(int i=1;i<=points;i++)
{
flag[i]=0;
}
flag[1]=1;
int min,u;
for(int i=1;i<=points-1;i++)
{
//源点到源点不用比较，因此总的次数少一次
min=infinity;
for(int j=1;j<points;j++)
{
if(flag[j]==0&&dis[j]<min)
{
//核心思想：依次比较出离源点最近的点
min=_____(4)______;
u=j;
}
}
flag[u]=1;
for(int v=1;v<=points;v++)
{
//找出离源点最近的点后更新dis里面的源点到各个点的值是否最小
if(edg[u][v]<infinity)
{
if(dis[v]>dis[u]+edg[u][v])
{
dis[v]=_____(5)______
}
}
}
}
for(int i=1;i<=points;i++)
{
cout<<dis[i]<<" ";
}
cout<<endl;
return 0;
}
