本文介绍最短路径Dijkstra算法，后文带有c语言代码（带批注）。

下面我们先来看一个例子

我们接下来将算A到各点的最短路程，首先我们知道，A到点A的距离是0，然后我们假设A到其他的的距离都为无穷大。接下来我们将从A开始行走。

接下来我们将从A走到B与D,并且我们将A标记，代表我们已经走过（之后不再访问）将到（A到A的距离）+（A到B的距离）与B存储在表格中的最短路程进行对比，如果小于，则交换。D同理，为此我们得到

接下来我们就要选则没被标记过得点中路程最短的点（此处贪心），易知道是D点，按照上面一样的步骤我们得到

此时已经标记过A，D，同上方法

此时A，D，E已经被标记

最终依次得到A到个点的最短路程。

下面附上c语言代码

Dijkstra算法 C语言实现

#include<stdio.h>

#include<stdlib.h>

#define max1 10000000 //假设无穷大

int a[1000][1000];//存储权值

int d[1000];//d表示源节点到该节点的最小距离

int p[1000];//p标记访问过的节点

int i, j, k;

int m;//m代表边数

int n;//n代表点数

int main()

{

scanf("%d%d",&n,&m);

int min1;

int x,y,z;

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&z);

a[x][y]=z;

a[y][x]=z; //无向图所以来回权值都设置成z

}

for( i=1; i<=n; i++)

d[i]=max1; //假设每个最短路径都是无穷大

d[1]=0; //从自己这个点开始走，到自己的距离最小一定是0

for(i=1;i<=n;i++)

{

min1 = max1; //先假设min1是无限大

for(j=1;j<=n;j++)

if(!p[j]&&d[j]<min1)//选出未访问节点中d[j]值最小的那个节点，并标记下一个访问节点k。

{

min1=d[j];

k=j;

}

//p[k]=d[k]; // 这是原来的代码，用下一 条代码替代。初始时，执行到这里k=1，而d[1]=0

//从而p[1]等于0，这样的话，上面的循环在之后的每次执行之后，k还是等于1。

p[k] = 1; //置1表示第k个节点已经访问过了。

for(j=1;j<=n;j++)

if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])//判断那一条路径最短

d[j]=d[k]+a[k][j];

}

//最终输出从源节点到其他每个节点的最小距离

for(i=1;i<n;i++)

printf("%d->",d[i]);

printf("%d\n",d[n]);

return 0;

}