社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。
基本思想
通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。
此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是"起点s到该顶点的路径"。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 ... 重复该操作,直到遍历完所有顶点。
操作步骤
(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。
(2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。
(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4) 重复步骤(2)和(3),直到遍历完所有顶点。
单纯的看上面的理论可能比较难以理解,下面通过实例来对该算法进行说明。
如下图有权图,Dijkstra算法可以计算任意节点到其他节点的最短路径
算法图解
1.选定A节点并初始化,如上述步骤3所示
2.执行上述 4、5两步骤,找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' )
来更新U集合
3.这时候 A->B, A->C
都为3,没关系。其实这时候他俩都是最短距离,如果从算法逻辑来讲的话,会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' )
,如图所示这时候A->B
距离 其实为 A->D->B
c# 代码实现
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 迪杰斯特拉算法
{
struct Graph
{
public char[] vexs; // 顶点集合
public int vexnum; // 顶点数
public int edgnum; // 边数
public int[,] matrix; // 邻接矩阵
};
class Program
{
static void Main(string[] args)
{
Graph g;
g.vexs = new char[]{'A','B','C','D','E'};
g.vexnum = 5;
g.edgnum = 7;
g.matrix = new int[5,5]{
{0,4,int.MaxValue,2,int.MaxValue},
{4,0,4,1,int.MaxValue},
{int.MaxValue,4,0,1,3},
{2,1,1,0,7},
{int.MaxValue,int.MaxValue,3,7,0}
};
dijkstra(g,0);
Console.ReadKey();
}
private static void dijkstra(Graph g,int vs)
{
int k = vs;
int min = int.MaxValue;
int tmp;
int[] flag = new int[100]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
int[] dist = new int[100];
int[] prev = new int[100];
for (int i = 0; i < g.vexnum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = g.matrix[vs, i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对 vs 进行初始化
flag[vs] = 1;
dist[vs] = 0;
for (int i = 1; i < g.vexnum; i++)
{
min = int.MaxValue;
for (int j = 0; j < g.vexnum; j++)
{
if (flag[j] == 0 && dist[j] < min)
{
min = dist[j];
k = j;
}
}
flag[k] = 1;
for (int n = 0; n < g.vexnum; n++)
{
tmp = g.matrix[k, n] == int.MaxValue ? int.MaxValue : (min + g.matrix[k, n]);
if (flag[n] == 0 && tmp < dist[n])
{
dist[n] = tmp;
prev[n] = k;
}
}
}
for (int i = 0; i < g.vexnum; i++)
{
Console.WriteLine("点:" + g.vexs[vs] + " 到点:" + g.vexs[i] + "的最短距离为:" + dist[i]);
}
}
}
}
运行结果
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!