汉扬编程 编程大纲 最短路径—Dijkstra算法(计算机学习)

最短路径—Dijkstra算法(计算机学习)

本文介绍最短路径Dijkstra算法,后文带有c语言代码(带批注)。

最短路径—Dijkstra算法(计算机学习)

下面我们先来看一个例子

最短路径—Dijkstra算法(计算机学习)

最短路径—Dijkstra算法(计算机学习)

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

最短路径—Dijkstra算法(计算机学习)

最短路径—Dijkstra算法(计算机学习)

接下来我们将从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;

}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6060.html

直播答题火了!一个简单的猜数小游戏C语言编程基础入门学习实现

五种C语言非数值计算的常用经典排序算法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部