1. (程序题)

输入有向图的相关信息，使用Dijkstra算法，求源点到其余顶点的最短路径长度。

注意：

（1）使用邻接矩阵存储图的信息

（2）按路径长度递增的次序产生最短路径并输出

        若源点到某顶点无路径，则放在最后输出。如：0到1无路径。

输入说明：

第一行输入有向图的顶点数、边数

第二行输入各顶点的值

接下来的若干行，输入各边的信息。输入格式：起始顶点 终止顶点 权值

最后输入源点的值

输出说明：

输出源点到其余顶点的最短路径长度（其中的冒号为中文全角标点符号）

输入样例：

6 8

0 1 2 3 4 5

0 2 10

0 4 30

0 5 100

1 2 5

2 3 50

3 5 10

4 3 20

4 5 60

0

输出样例：

0到2的最短路径长度：10

0到4的最短路径长度：30

0到3的最短路径长度：50

0到5的最短路径长度：60

0到1无路径

代码实现

其实可以定义一个结构体的，放到一块更容易操作。不然掉来调去太麻烦了。

#include <stdio.h>
#include <limits.h>
#include<stdlib.h>

#define MAX_VERTICES 100

//查找顶点
int FindIndex(char* values,int numVertices,char val) {
    for (int i = 0; i < numVertices; i++) {
        if (values[i] == val) {
            return i;
        }
    }
    return -1;
}

// Dijkstra算法求最短路径
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices, int srcIndex,char* values) {
    int dist[MAX_VERTICES]; // 保存源点到各顶点的最短路径长度
    int visited[MAX_VERTICES]; // 标记顶点是否被访问过

    // 初始化距离和访问标记数组
    for (int i = 0; i < numVertices; ++i) {
        dist[i] = INT_MAX; // 初始化距离为无穷大
        visited[i] = 0; // 初始化未访问
    }

    // 源点到自身的距离为0
    dist[srcIndex] = 0;

    // 计算最短路径长度
    for (int count = 0; count < numVertices - 1; ++count) {
        // 选取当前距离最短且未访问过的顶点
        int minDist = INT_MAX;
        int minIndex = -1;
        for (int v = 0; v < numVertices; ++v) {
            if (!visited[v] && dist[v] < minDist) {
                minDist = dist[v];
                minIndex = v;
            }
        }

        // 标记该顶点已访问
        visited[minIndex] = 1;

        // 更新相邻顶点的最短路径长度
        for (int v = 0; v < numVertices; ++v) {
            if (!visited[v] && graph[minIndex][v] && dist[minIndex] != INT_MAX &&
                dist[minIndex] + graph[minIndex][v] < dist[v]) {
                dist[v] = dist[minIndex] + graph[minIndex][v];
            }
        }
    }
    int* path = (int*)malloc(sizeof(int) * numVertices);
    //assert(path);
    for (int i = 0; i < numVertices; i++) {
        path[i] = i;
    }
    // 对最短路径长度进行排序
    for (int i = 0; i < numVertices - 1; ++i) {
        for (int j = i + 1; j < numVertices; ++j) {
            if (dist[i] > dist[j]) {
                int temp = dist[i];
                dist[i] = dist[j];
                dist[j] = temp;
                int tmp = path[i];
                path[i] = path[j];
                path[j] = tmp;
            }
        }
    }

    // 输出最短路径长度
    for (int i = 0; i < numVertices; ++i) {
        if (path[i] != srcIndex && dist[i] != INT_MAX) {
            printf("%c到%c的最短路径长度：%d\n", values[srcIndex], values[path[i]], dist[i]);
        }
        else if (dist[i] == INT_MAX) {
            printf("%c到%c无路径\n", values[srcIndex], values[path[i]]);
        }
    }
}

int main() {
    int numVertices, numEdges;
    scanf("%d %d", &numVertices, &numEdges);

    int graph[MAX_VERTICES][MAX_VERTICES] = { 0 }; // 初始化邻接矩阵

    // 读取顶点的值
    char values[MAX_VERTICES] = { 0 };
    for (int i = 0; i < numVertices; ++i) {
        scanf(" %c", &values[i]);
    }

    // 读取边的信息
    for (int i = 0; i < numEdges; ++i) {
        char src = 0, dest = 0;
        int weight = 0;
        scanf(" %c %c %d", &src, &dest, &weight);
        int srcIndex = FindIndex(values, numVertices,src);
        int destIndex = FindIndex(values,numVertices,dest);
        graph[srcIndex][destIndex] = weight; // 添加有向边
    }

    // 输入源点的值
    char srcValue;
    scanf(" %c", &srcValue);

    // 查找源点在顶点值数组中的索引
    int srcIndex = FindIndex(values, numVertices, srcValue);


    // 如果源点在图中不存在，则输出无路径
    if (srcIndex == -1) {
        printf("%d到%d无路径\n", srcValue, srcValue);
    }
    else {
        // 执行Dijkstra算法
        dijkstra(graph, numVertices, srcIndex,values);
    }

    return 0;
}

2. (程序题)

输入有向图的相关信息，使用Floyd算法，求每对顶点之间的最短路径长度。

注意：

（1）使用邻接矩阵存储图的信息

（2）辅助数组D，记录顶点vi和vj之间的最短路径长度

（3）辅助数组Path，记录最短路径上顶点vj的前一顶点的序号

输入说明：

第一行输入有向图的顶点数、边数

第二行输入各顶点的值

接下来的若干行，输入各边的信息。输入格式：起始顶点 终止顶点 权值

输出说明：

输出每对顶点之间的最短路径长度及最短路径上前驱顶点的序号；

若两个顶点之间无路径，则最短路径长度用“#”表示，最短路径上前驱顶点的序号用“-1”表示；

注意，最短路径长度占4个宽度，右对齐；前驱顶点的序号占2个宽度，右对齐，并用英文半角的圆括号括起来

输入样例1：

4 8

0 1 2 3

0 1 1

0 3 4

1 2 9

1 3 2

2 0 3

2 1 5

2 3 8

3 2 6

输出样例1：

0(-1) 1( 0) 9( 3) 3( 1)

11( 2) 0(-1) 8( 3) 2( 1)

3( 2) 4( 0) 0(-1) 6( 1)

9( 2) 10( 0) 6( 3) 0(-1)

输入样例2：

5 8

A B C D E

A B 10

A D 30

A E 99

B C 50

B D 40

C E 10

D C 20

D E 60

输出样例2：

0(-1) 10( 0) 50( 3) 30( 0) 60( 2)

#(-1) 0(-1) 50( 1) 40( 1) 60( 2)

#(-1) #(-1) 0(-1) #(-1) 10( 2)

#(-1) #(-1) 20( 3) 0(-1) 30( 2)

#(-1) #(-1) #(-1) #(-1) 0(-1)

代码实现

其实这里也可以定义一个结构体的，放到一块更容易操作。

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100

// Floyd算法求每对顶点之间的最短路径长度
void floyd(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices) {
    int dist[MAX_VERTICES][MAX_VERTICES]; // 保存每对顶点之间的最短路径长度
    int path[MAX_VERTICES][MAX_VERTICES]; // 记录最短路径上的前驱顶点

    // 初始化距离和路径数组
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            dist[i][j] = graph[i][j]; // 初始化距离为邻接矩阵中的权值
            if (i != j && graph[i][j] < INT_MAX) {
                path[i][j] = i; // 如果有路径，则路径的前驱顶点为i
            }
            else {
                path[i][j] = -1; // 否则为-1
            }
        }
    }

    // 计算每对顶点之间的最短路径长度
    for (int k = 0; k < numVertices; ++k) {
        for (int i = 0; i < numVertices; ++i) {
            for (int j = 0; j < numVertices; ++j) {
                if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX &&
                    dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短路径长度
                    path[i][j] = path[k][j]; // 更新最短路径上的前驱顶点
                }
            }
        }
    }

    // 输出每对顶点之间的最短路径长度及路径上前驱顶点的序号
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (dist[i][j] == INT_MAX) {
                printf("%4c(%2d)", '#', -1);
            }
            else {
                printf("%4d(%2d)", dist[i][j], path[i][j]);
            }
        }
        printf("\n");
    }
}

int main() {
    int numVertices, numEdges;
    scanf("%d %d", &numVertices, &numEdges);

    int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵存储图的信息

    // 读取顶点的值
    char values[MAX_VERTICES][2]; // 假设顶点的值是单个字符
    for (int i = 0; i < numVertices; ++i) {
        scanf(" %c", &values[i][0]);
    }

    // 初始化邻接矩阵
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (i == j) {
                graph[i][j] = 0; // 自身到自身的距离为0
            }
            else {
                graph[i][j] = INT_MAX; // 其他距离初始化为无穷大
            }
        }
    }

    // 读取边的信息并构建邻接矩阵
    for (int i = 0; i < numEdges; ++i) {
        char src, dest;
        int weight;
        scanf(" %c %c %d", &src, &dest, &weight); // 空格用于跳过换行符
        int srcIndex, destIndex;
        for (int j = 0; j < numVertices; ++j) {
            if (values[j][0] == src) {
                srcIndex = j;
            }
            if (values[j][0] == dest) {
                destIndex = j;
            }
        }
        graph[srcIndex][destIndex] = weight; // 添加有向边的权值
    }

    // 使用Floyd算法求解最短路径
    floyd(graph, numVertices);

    return 0;
}

---

---