1.软件版本
matlab2022a
2.运行方法
使用matlab2022a或者高版本仿真,运行文件夹中的tops.m或者main.m。运行时注意matlab左侧的当前文件夹窗口必须是当前工程所在路径。具体操作观看提供的程序操作视频跟着操作。视频播放使用windows media player播放。
3.部分仿真截图
4.内容简介
负环的定义:负环是指权值和为负数的环。负环会使图的最短路径计算陷入死循环,因此,存在负环的图不存在最短路。
负环的计算方法:
负环有两种计算方法,都是基于Bellman-Ford算法或者SPFA算法。
第一种算法是:统计每个点的入队次数,如果某个点入队大于等于n次,则说明有负环
第二种算法是:统计到某个点的最短路所经过点的个数,如果经过n个点,则说明存在负环。
(一般情况下,我们使用第二种算法)
由于当负环存在时,SPFA会陷入死循环,且n是非死循环的最坏情况。所以以上两种算法是正确的。
求负环算法的编程实现
首先将所有点的距离都赋值为0
然后将所有的点入队。