void Hungarian::Init() { int i, j; //Khởi tạo ban đầu 2 bộ ghép đều rỗng (các giá trị được gán bằng -1 nghĩa là chưa có // đỉnh X gán với Y hoặc ngược lại) for (i = 0; i < MAX; i++) { matchX[i] = -1; matchY[i] = -1; } //tìm trọng số nhỏ nhất của các cạnh liên thuộc với X[i] for (i = 0; i < k; i++) { Fx[i] = maxC; for (j = 0; j < k; j++) { if (c[i][j] < Fx[i]) { Fx[i] = c[i][j]; } } } //tìm trọng số nhỏ nhất của các cạnh liên thuộc với Y[j] for (j = 0; j < k; j++) { Fy[j] = maxC; for (i = 0; i < k; i++) { if (c[i][j] - Fx[i] < Fy[j]) { Fy[j] = c[i][j] - Fx[i]; } } } }
时间: 2023-06-16 14:06:33 浏览: 107
Hungarian:匈牙利算法java实现
这段代码是匈牙利算法的初始化函数,主要实现以下几个任务:
1. 初始化匹配数组matchX和matchY,初始时没有顶点被匹配,所以数组中所有值都为-1。
2. 对于每个顶点X[i],计算其与相邻顶点Y[j]之间边的最小权值,并将其保存在Fx[i]中。
3. 对于每个顶点Y[j],计算与相邻顶点X[i]之间边的权值减去Fx[i]的最小值,并将其保存在Fy[j]中。
以上步骤是匈牙利算法的预处理步骤,在找增广路时会用到这些信息。其中,maxC是一个较大的常数,起到初始化Fx和Fy时的默认最大值的作用。
阅读全文