dijkstra算法解决3杯倒水问题

a, b, c = 12, 9, 5
cnt = []
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if i + j + k == 12:
                cnt.append([i, j, k])
cnt.reverse()
print(cnt)
print(len(cnt))
print("6,6,0 index:", cnt.index([6, 6, 0]))


def move(x, y, max, r=0):
    tmp = abs(max - y)
    x_ = x if x < tmp else tmp
    t = [x - x_, y + x_]
    if r:
        t.reverse()
    return t


def check(x, y):
    M = 1E100
    if x == y:
        return 0
    tmp = []
    tmp.append(move(x[0], x[1], 9) + [x[2]])  # a->b
    k = move(x[0], x[2], 5)
    k.insert(1, x[1])
    tmp.append(k)  # a->c
    tmp.append(move(x[1], x[0], 12, 1) + [x[2]])  # b->a
    tmp.append([x[0]] + move(x[1], x[2], 5))  # b->c
    k = move(x[2], x[0], 12, 1)
    k.insert(1, x[1])
    tmp.append(k)  # c->a
    tmp.append([x[0]] + move(x[2], x[1], 9, 1))  # c->b
    if y in tmp:
        return 1
    return M


def generate_matrix():
    nums = []
    for index, i in enumerate(cnt):
        tmp_x = []
        for j in cnt:
            r = check(i, j)
            tmp_x.append(r)
        nums.append(tmp_x)
    print(nums)
    return nums


def dijkstra(matrix, source):
    M = 1E100
    n = len(matrix)
    m = len(matrix[0])
    if source >= n or n != m:
        print('Error!')
        return
    found = [source]  # 已找到最短路径的节点
    cost = [M] * n  # source到已找到最短路径的节点的最短距离
    cost[source] = 0
    path = [[]] * n  # source到其他节点的最短路径
    path[source] = [source]
    while len(found) < n:  # 当已找到最短路径的节点小于n时
        min_value = M + 1
        col = -1
        row = -1
        for f in found:  # 以已找到最短路径的节点所在行为搜索对象
            for i in [x for x in range(n) if x not in found]:  # 只搜索没找出最短路径的列
                if matrix[f][i] + cost[f] < min_value:  # 找出最小值
                    min_value = matrix[f][i] + cost[f]  # 在某行找到最小值要加上source到该行的最短路径
                    row = f  # 记录所在行列
                    col = i
        if col == -1 or row == -1:  # 若没找出最小值且节点还未找完，说明图中存在不连通的节点
            break
        found.append(col)  # 在found中添加已找到的节点
        cost[col] = min_value  # source到该节点的最短距离即为min_value
        path[col] = path[row][:]  # 复制source到已找到节点的上一节点的路径
        path[col].append(col)  # 再其后添加已找到节点即为sorcer到该节点的最短路径
    return found, cost, path


def run(index):
    matrix = generate_matrix()
    found, cost, path = dijkstra(matrix, 0)
    print('found:')
    print(found)
    print('cost:')
    print(cost[21])
    print('path:')
    for p in path:
        if p and p[-1] == index:
            print(p)
            for j in p:
                print(cnt[j], "->", end="")


run(21)