温馨提示：这个题是我在面Node后端的时候遇到的一道算法题，当时没有写出来，所以记录一下，以后再遇到类似的题可以参考一下。

火车站点路线规划问题

题目详情

• 当地的通勤铁路服务于许多城镇。所有的轨道都是“单向的”。也就是说，从a镇到B镇的路线并不意味着从B镇到a镇的路线的存在。事实上，即使这两条路线确实存在，它们也是不同的，而且不一定是相同的距离!

• 这个问题的目的是帮助铁路公司向客户提供有关路线的信息。特别是，你将计算沿着某条路线的距离，两个城镇之间不同路线的数量，以及两个城镇之间最短的路线。

• 输入:一个有向图，其中一个节点代表一个城镇，一条边代表两个城镇之间的路线。边缘的权重表示两个城镇之间的距离。给定的路线只会出现一次，并且对于给定的路线，起始城镇和结束城镇不会是同一个城镇。

• 输出:对于测试输入1 ~ 5，如果没有这样的路路线存在。否则，按照给出的路线进行;不要做任何额外的停留!例如，第一个问题意味着从A市出发，然后直接前往B市(距离5)，然后直接前往C市(距离4)。

条件如下

1. 站点=>站点线路是单向的。
2. A站点=>B站点的线路存在，未必B=>A存在，即使AB和BA存在，AB未必等于BA。
3. 计算沿着某条路线的距离，两个城镇之间不同路线的数量，以及两个城镇之间最短的路线。
4. 图:AB=5, BC=4, CD=8, DC=8, DE=6, AD=5, CE=2, EB=3, AE=7

解决方案

ps:因为当时接触的算法不多，所以查阅资料一下解决方法挺多的，当前我只接触了dijkstra算法所以我使用这个算法。

1.定义节点信息和图详情

//  站点信息 
interface Site {
    /**名字 */
    name: string,
    /**距离 */
    distance: number,
}

// 路线图
interface Graph {
    [key: string]: Site[]
}
// 站点图
const graph: Graph = {
    A: [{ name: 'B', distance: 5 }, { name: 'D', distance: 5 }, { name: 'E', distance: 7 }],
    B: [{ name: 'C', distance: 4 }],
    C: [{ name: 'D', distance: 8 },{ name: 'E', distance: 2 }],
    D: [ { name: 'C', distance: 8 },{ name: 'E', distance: 6 }],
    E: [{ name: 'B', distance: 3 }, ]
};

2.dijkstra算法推导最近路线

根据起点和终点推断最近路线，没有则返回null

function dijkstra(graph: Graph, start: string, end: string): null | number {
    /** 记录每个节点到start的距离 */
    const distance: { [key: string]: number } = {}
    /** 存储每个节点前一个节点，用于重选路径 */
    const previous: { [key: string]: string | null } = {};
    /** 获取图中所有站点 */
    const site_list = Object.keys(graph)
    site_list.forEach(site => {
        // 因为定义了类型值为number,初始值不知道，所以定义无穷大
        distance[site] = Infinity
        // 设置前一个节点为null
        previous[site] = null
    })
    // 初始化起点
    distance[start] = 0
    while (site_list.length > 0) {
        // minDis 最小距离 dis前节点距离
        // 此处循环站点 得到最近站点
        const site_name = site_list.reduce((minDis, dis) => distance[dis] < distance[minDis] ? minDis : dis)
        // 如果站点为终点，则结束循环
        if (site_name === end) break;
        // 删除已经处理过的站点
        site_list.splice(site_list.indexOf(site_name), 1)
        // 循环当前站点，获取下一个站点
        graph[site_name].forEach(site => {
            // 计算当前站点到下一个站点的距离
            const dis = distance[site_name] + site.distance
            // 如果距离小于当前站点到下一个站点的距离，则更新距离和前一个站点
            if (dis < distance[site.name]) {
                distance[site.name] = dis
                previous[site.name] = site_name
            }
        })
    }
    return distance[end] === Infinity ? null : distance[end]
}

3.dfs深度优先搜索路径

查找起点到终点的满足条件的所有路径

/**
 * 深度优先搜索
 * @param graph 站点图
 * @param start 起点站
 * @param end 终点站
 * @param path 当前路径
 * @param paths 所有路径
 */
function dfs(graph: Graph, start: string, end: string, path: string[], paths: string[]): void {
    // 当前路线情况
    path.push(start);
    // 如果起点站等于终点站，则将当前路径加入所有路径
    if (start === end) {
        paths.push(path.join('-'));
    } else {
        // 如果起点站不是终点站，则循环当前站点的所有路线
        graph[start].forEach(edge => {
            dfs(graph, edge.name, end, path, paths);
        });
    }
    // 回溯，将当前站点从路径中删除
    path.pop();
}

4.获得所有路径

/**
 * 计算路径
 * @param graph 站点图
 * @param start 起点
 * @param end 终点
 * @returns 结果
 */
function countRoutes(graph: Graph, start: string, end: string): number {
    const paths: string[] = [];
    dfs(graph, start, end, [], paths);
    return paths.length;
}

总结

通过dijkstra算法获取最短路径，通过dfs获取所有路径，最终得到结果。

这未必是最好的解决方案，但是就目前我能了解到的，这是我能想出来做出功能的方案。