# longest path

{% tabs %}
{% tab title="code" %}

* replit ⟩ [Multiple-Factor Sequence (longest path problem)](https://replit.com/@pegasusroe/Multiple-Factor-Sequence-longest-path-problem#index.js)  

```javascript
// 「因數倍數」關係
function isConnected(a, b) {
    return a != b && (a % b == 0 || b % a == 0);
}

// 生成 1 ... N 的「因數倍數」連結圖
function generateGraph(N) {
    // 剛開始是一個空的 dictionary (key: 1 ... N, value: 該數的「因數或倍數」)
    let graph = {};
    // 找出 1 ... N 每個數的「因數或倍數」
    for (let i = 1; i <= N; i++) {
        let neighbors = [];
        for (let j = 1; j <= N; j++) {
            if (isConnected(i, j)) neighbors.push(j + '');  // int -> string
        }
        graph[i] = neighbors;
    }
    // 回傳 dictionary
    return graph;
}

// 找出 1 ... N 的最長「因數倍數數列」
function longestPath(N, {debug = false}={}) {

    // 紀錄執行開始時間
    const startTime = Date.now();

    // 生成「因數倍數」連結圖
    const neighbors = generateGraph(N);

    // 初始設定
    let maxPathLength = 0;    // 最長路徑長度
    let result = [];          // 最長路徑

    // 深度優先搜尋(depth-first-search)
    function dfs(node, currentLength, visited) {

        // 標記「當前節點」為「已訪問」
        visited.add(node);
        // 更新當前路徑長度
        currentLength++;

        // 更新最長路徑長度
        if (currentLength > maxPathLength) {
            maxPathLength = currentLength;
            result = Array.from(visited).map(x => +x);
            if (debug) console.log('當前長度：', result.length, '，當前路徑：', result + '');
        }

        // 對當前節點的每個鄰居進行深度優先搜尋
        for (let neighbor of neighbors[node]) {
            if (!visited.has(neighbor)) dfs(neighbor, currentLength, visited);
        }
        
        // 回溯前将當前節點標記為「未訪問」
        visited.delete(node);
    }

    // 對每個節點進行深度優先搜尋
    for (let node in neighbors) {
        dfs(node, 0, new Set());
    }

    console.log('N =', N);
    console.log('最長長度:', maxPathLength);
    console.log('最長路徑:', result + '');
    console.log('執行時間：', Date.now() - startTime, 'ms');
}

// run
longestPath(15, {debug: true});
```

{% endtab %}

{% tab title="code 2" %}

* replit ⟩&#x20;
  * [Multiple-Factor Sequence (longest path problem)](https://replit.com/@pegasusroe/Multiple-Factor-Sequence-longest-path-problem#index.js)&#x20;
  * [longest path problem (undirected graph)](https://replit.com/@pegasusroe/longest-path-problem-undirected-graph#index.js)&#x20;
    {% endtab %}

{% tab title="📗 參考" %}

* [ ] GeeksOfGeeks ⟩ [**Longest Path in a Directed Acyclic Graph**](https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/)
* [ ] Wiki ⟩ [Longest path problem](https://en.wikipedia.org/wiki/Longest_path_problem) &#x20;
* [ ] ChatGPT ⟩ [尋找最長路徑](https://chat.openai.com/share/ca7be066-0d95-4a7c-8b98-cd6d85b76d5f)&#x20;
* [ ] desmos ⟩ [最長因數倍數數列](https://www.desmos.com/calculator/roclzyeyub)  (估算執行所需時間)
  {% endtab %}
  {% endtabs %}