数据结构 最少换车次数

Question

问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车都是单向的，这n个车站被顺序编号为0至n-l。本程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号，求从站0出发乘公交车至站n-1的最少换车次数。要求：1）利用输入信息构建一张有向图（用邻接矩阵表示）。2）求从站0出发乘公交车至站n-1的最少换车次数。

Answer 1

这是一个经典的动态规划问题，称为旅行商问题（Traveling Salesman Problem, TSP）。在这个问题中，我们希望找到访问一系列城市并返回起点的最短路径，其中每条路径只允许经过每个城市一次。

以下是一个使用C语言和动态规划解决这个问题的示例代码：

c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATIONS 100
#define INF 100000000

int graph[MAX_STATIONS][MAX_STATIONS];
int dist[MAX_STATIONS][MAX_STATIONS];
int visited[MAX_STATIONS];
int n;

void fill_graph() {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i == j) {
                graph[i][j] = 0;
            } else {
                graph[i][j] = INF;
            }
        }
    }
    for (i = 0; i < m; i++) {
        int u = lines[i][0] - 1;
        int v = lines[i][1] - 1;
        graph[u][v] = 1; // graph is undirected, so also graph[v][u] = 1
    }
}

void fill_dist() {
    int i, j, k;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            dist[i][j] = INF;
        }
    }
    for (i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (graph[i][j] != INF) {
                dist[i][j] = graph[i][j];
            } else {
                for (k = 0; k < n; k++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }
}

int tsp() {
    int i, j, k, min, count = 0;
    visited[n-1] = 1; // start from station n-1 and go to station 0 with at least one more stop in between
    for (i = n-2; i >= 0; i--) { // go from n-2 to 0, because we already visited n-1 in the previous step
        min = INF;
        for (j = 0; j < n; j++) { // find the next station to visit from station i
            if (visited[j] == 0 && dist[i][j] != INF && dist[i][j] < min) { // choose the closest station that hasn't been visited yet and is reachable from station i
                k = j;
                min = dist[i][j]; // remember the minimum distance to the chosen station and update min value if necessary in the next step
            }
        }
        visited[k] = 1; // mark the chosen station as visited for the next step in the loop above (from i-1 to 0)
        count++; // count the number of stations visited in this step (from n-2 to 0) including the start station (n-1) and the chosen station k in this step
    }
    return count - 1; // return the number of stations visited minus one (because we started from station n-1 and ended at station 0) to get the number of changes needed to reach station n-1 from station 0, excluding the last change which brings us back to station 0 at the end of the trip. We need to subtract one because we count the start and end stations as one change each. If we started from station 0 and ended at station n-1, we would need count+1 changes. In this case, we started from station n-1 and ended at station 0, so we need