matlab编写算法

Ⅰ 怎样用matlab编程实现Dijkstra算法

Dijkstra算法是一种用于寻找最短路径的搜索算法，由荷兰科学家提出。该算法通过为每个节点保留目前为止所找到的从起点到该节点的最短路径。为了记录最佳路径轨迹，需要记录路径上每个节点的前趋，通过回溯法找出最短路径轨迹。

在尝试找到一个Matlab版本实现时，我发现现有的实现存在一些问题。经过修改，得到了一种较为有效的实现方式。下面是一个Matlab函数，用于实现Dijkstra算法：

[distance path] = Dijk(W,st,e)

该函数接收权值矩阵W，起点st和终点e作为输入参数。具体实现如下：

首先定义节点数n，计算起点到各节点的距离D，并初始化visit数组用于记录节点访问状态。parent数组用于记录每个节点的前趋节点，path数组用于存储最短路径。接下来进行循环，寻找最短距离的下一个点，每次不会重复原来的轨迹，通过visit判断节点是否访问。然后更新路径长度和前趋节点，以便后续回溯循迹。最后，通过回溯法找到最短路径，返回最短距离和路径。

测试用例1：

权值矩阵W如下：

[0 50 inf 40 25 10 50 0 15 20 inf 25 inf 15 0 10 20 inf 40 20 10 0 10 25 25 inf 20 10 0 55 10 25 inf 25 55 0]

测试代码：

[distance,path]=Dijk(W,1,4)

运行结果：

distance = 35

path = 1 6 4

从节点1到节点4的最短距离路径为1-->6-->4，最短距离为35。

通过这种方法，可以有效地实现Dijkstra算法，并找到从起点到终点的最短路径。