c - 带隧道的路线图

Question

给定多个城市之间的路线图，其中 2 个城市之间的道路包含隧道，您的目标是找到起始城市和所有其他城市之间的最短路径，以便每条路径至少包含一个隧道。 (问题并不总是有解决方案)。假设道路的成本是给定的。输入 - 来自文件，输出 - 到文件，包含起始城市和到其余城市的路径。

现在我尝试用 Dijkstra 的算法来做到这一点，它解决了我的大部分问题，除了必须使用隧道的部分。谁能帮我这个？这是我的代码。提前致谢!

文件输入:

10

1 2 10

1 4 5

2 3 1

2 4 3

3 5 6

4 2 2

4 3 9

4 5 2

5 1 7

5 3 4

#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE];/* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE]; /* prev[i] is the node that comes right before i in the shortest path from the source to i*/ 

void printD() {
int i;

printf("Distances:\n");
for (i = 1; i <= n; ++i)
    printf("%10d", i);
printf("\n");
for (i = 1; i <= n; ++i) {
    printf("%10ld", d[i]);
}
printf("\n");
}

/*
 * Prints the shortest path from the source to dest.
 * dijkstra(int) MUST be run at least once BEFORE
 * this is called
 */
void printPath(int dest) {
    if (prev[dest] != -1)
        printPath(prev[dest]);
    printf("%d ", dest);
}

void dijkstra(int s) {
    int i, k, mini;
    int visited[GRAPHSIZE];

    for (i = 1; i <= n; ++i) {
        d[i] = INFINITY;
        prev[i] = -1; /* no path has yet been found to i */
        visited[i] = 0; /* the i-th element has not yet been visited */
    }

d[s] = 0;

for (k = 1; k <= n; ++k) {
    mini = -1;
    for (i = 1; i <= n; ++i)
        if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
            mini = i;

    visited[mini] = 1;

    for (i = 1; i <= n; ++i)
        if (dist[mini][i])
            if (d[mini] + dist[mini][i] < d[i]) {
                d[i] = d[mini] + dist[mini][i];
                prev[i] = mini;
            }
}
}

int main(int argc, char *argv[]) {
    int i, j;
    int u, v, w;

FILE *fin = fopen("dist.txt", "r");
/*    the first line contains e, the number of edges the following e lines
contain 3 numbers: u, v and w signifying that there’s an edge from u to v of weight w*/
fscanf(fin, "%d", &e);
for (i = 0; i < e; ++i)
    for (j = 0; j < e; ++j)
        dist[i][j] = 0;
n = -1;
for (i = 0; i < e; ++i) {
    fscanf(fin, "%d%d%d", &u, &v, &w);
    dist[u][v] = w;
    n = MAX(u, MAX(v, n));
}
fclose(fin);

dijkstra(1);

printD();

printf("\n");
for (i = 1; i <= n; ++i) {
    printf("Path to %d: ", i);
    printPath(i);
    printf("\n");
}

return 0;
}

Answer 1

运行 Dijkstra 算法找到从起始城市到所有隧道的所有最短路径。

以所有隧道为起点再次运行 Dijkstra 算法，以找到到所有其他城市的所有最短路径。所以你会从 Dijkstra 算法的中间开始，你的 priority queue 中已经有一堆候选者(所有隧道)。 , 所有这些都将被标记为已访问。

看起来您没有使用优先级队列(Dijkstra 算法的高效实现使用了优先级队列)，但我相信您会设法弄清楚如何将我的解决方案应用到您的代码中。