Dijkstra算法的Matlab/C++代码

Dijkstra算法,中文名迪杰斯特拉算法,是图论中最常用的算法之一,用来解决图中一个点到其他所有点的最短路问题。Dijkstra算法的Matlab代码和C++代码其实网上很多,但是我还是给出我自己写的,感觉比网上那些用起来方便多了。C++的是通信网理论基础课上的作业,绝对不会有问题。Matlab的已经经历我多次做题的考验了,从未出现过问题…… Continue reading “Dijkstra算法的Matlab/C++代码”

匈牙利算法 Matlab/C++代码

匈牙利算法是为了解决二分图的最大匹配问题。其算法核心,其实就是不停的寻找增广路径,然后进行替换。这里引用Matrix67对其的理解,我觉得很精辟:

说穿了,就是你从二分图中找出一条路径来,让路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。不断执行上述操作,直到找不到这样的路径为止。

Continue reading “匈牙利算法 Matlab/C++代码”