在下图中找到节点之间的最短距离

Question

图是这样定义的，该图有N个节点，其中每个节点都分配了一个数字1 <= k <= N（每个数字只分配给一个节点）。如果 i 是 j 的最大整除数（i != j），则节点 i 和 j 之间存在一条边。给定两个节点，我需要找到它们之间的最短路径。

我认为这是一个简单的问题。我认为我需要做的就是用它们的最大整除数替换给定的两个数字，直到它们相等，然后简单地打印出我用它的整除数替换一个数字的次数。但是我没有通过所有测试（但是我的代码通过了示例测试）。

这是我使用的代码：

#include <stdio.h>
#include <iostream>
#include <math.h>  

using namespace std;

int biggest_divisor (int number) {
    for (int i = 2; i <= ceil (sqrt(number)) + 1; i++){
        if (number% i == 0){
            return number/ i;
        }
    }
    return 1;
}

int main(int argc, char **argv)
{

    int N, a, b;
    int a_steps = 0;
    int b_steps = 0;

    cin >> N >> a >> b;

    while (a != b){
        if (a > b){
            a = biggest_divisor (a);
            a_steps += 1;
        } 
        if (a < b) {
            b = biggest_divisor (b);
            b_steps += 1;
        }
    }
    cout << a_steps + b_steps;
}

Answer 1

完整的解决方案：

int biggest_divisor (int number) {
    for (int i = number / 2 ; i >= 1; i--){
        if (number% i == 0){
            return i;
        }
    }
    return 1;
}

int main(int argc, char* argv[])
{
    int N, a, b;
    int steps = 0;

    cin >> N >> a >> b;

    while (a != b) {
        (a > b) ? a = biggest_divisor (a) : b = biggest_divisor (b);
        steps++;
    }
    cout << steps;
}

在下图中找到节点之间的最短距离

Find shortest distance in between nodes in following graph

c++

graph