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;
}
