#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_VERTICES 100 #define INF INT_MAX typedef struct Graph { int V; //顶点数 int E; //边数 int adj[MAX_VERTICES][MAX_VERTICES];//邻接矩阵 } Graph; void init_graph(Graph* G, int V) { G->V = V; G->E = 0; for (int i = 0; i < G->V; i++) { for (int j = 0; j < G->V; j++) { G->adj[i][j] = INF; } } } void add_edge(Graph* G, int u, int v, int w) { G->adj[u][v] = w; G->adj[v][u] = w; G->E++; } void dijkstra(Graph* G, int s, int dist[]) { int visited[MAX_VERTICES] = { 0 }; for (int i = 0; i < G->V; i++) { dist[i] = INF; } dist[s] = 0; for (int i = 0; i < G->V; i++) { int u = -1; for (int j = 0; j < G->V; j++) { if (!visited[j] && (u == -1 || dist[j] < dist[u])) { u = j; } } visited[u] = 1; for (int v = 0; v < G->V; v++) { if (G->adj[u][v] != INF) { if (dist[u] + G->adj[u][v] < dist[v]) { dist[v] = dist[u] + G->adj[u][v]; } } } } } int main() { Graph G; int V = 6; init_graph(&G, V); add_edge(&G, 0, 1, 10); add_edge(&G, 0, 2, 3); add_edge(&G, 1, 2, 1); add_edge(&G, 1, 3, 2); add_edge(&G, 2, 1, 4); add_edge(&G, 2, 3, 8); add_edge(&G, 2, 4, 2); add_edge(&G, 3, 4, 7); add_edge(&G, 3, 5, 1); add_edge(&G, 4, 5, 5); int dist[MAX_VERTICES]; dijkstra(&G, 0, dist); printf("最短路径长度为:%d\n", dist[V - 1]); return 0; }代码解读
时间: 2024-03-31 20:32:38 浏览: 17
这是一个使用邻接矩阵实现的Dijkstra算法的代码。首先定义了一个图的结构体,包括顶点数、边数和邻接矩阵。然后定义了初始化图的函数和添加边的函数。接着是Dijkstra算法的实现,在算法中用visited数组记录已经访问过的顶点,用dist数组记录源点到各个顶点的最短距离,算法的核心循环是通过选择dist数组中最小的未访问过的顶点来进行松弛操作。最后在主函数中构造了一个图,并计算了从顶点0到顶点5的最短路径长度。
相关问题
c语言最小生成树邻接矩阵求权
以下是使用C语言求解最小生成树邻接矩阵权的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 100
#define INF INT_MAX
int n; // 图中节点数
int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int selected[MAX_VERTICES]; // 已选择的节点
int dist[MAX_VERTICES]; // 节点到最小生成树的距离
// Prim算法求解最小生成树
void prim(int start) {
int i, j, u, v, min;
// 初始化
for (i = 0; i < n; i++) {
dist[i] = adj[start][i];
selected[i] = 0;
}
selected[start] = 1;
// 选择n-1个节点
for (i = 0; i < n - 1; i++) {
min = INF;
u = -1;
// 选择距离最小的节点
for (j = 0; j < n; j++) {
if (!selected[j] && dist[j] < min) {
min = dist[j];
u = j;
}
}
selected[u] = 1;
// 更新距离
for (v = 0; v < n; v++) {
if (!selected[v] && adj[u][v] < dist[v]) {
dist[v] = adj[u][v]; }
}
}
}
int main() {
int i, j, start, sum = 0;
// 读入节点数和邻接矩阵
scanf("%d", &n);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
}
}
// 选择起始节点
printf("请输入起始节点:");
scanf("%d", &start);
// 求解最小生成树
prim(start);
// 计算最小代价
for (i = 0; i < n; i++) {
if (dist[i] != INF) {
sum += dist[i];
}
}
printf("最小生成树的代价为:%d\n", sum);
return 0;
}
```
图求最短路径c语言
最短路径算法有很多种,其中比较常见的是Dijkstra算法和Floyd算法。下面分别给出两种算法的C语言实现。
1. Dijkstra算法
Dijkstra算法是一种贪心算法,用于求解单源最短路径问题,即从给定的源点到所有其他点的最短路径。
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 100
#define INF INT_MAX
int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];
int num_vertices;
int get_min_distance_vertex() {
int min_distance = INF;
int min_vertex = -1;
for (int i = 0; i < num_vertices; i++) {
if (!visited[i] && dist[i] < min_distance) {
min_distance = dist[i];
min_vertex = i;
}
}
return min_vertex;
}
void dijkstra(int start) {
// 初始化
for (int i = 0; i < num_vertices; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[start] = 0;
// 迭代
for (int i = 0; i < num_vertices; i++) {
int u = get_min_distance_vertex();
visited[u] = 1;
for (int v = 0; v < num_vertices; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main() {
// 输入
printf("请输入顶点数:");
scanf("%d", &num_vertices);
printf("请输入图的邻接矩阵:\n");
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
scanf("%d", &graph[i][j]);
}
}
// 计算最短路径
printf("请输入起点:");
int start;
scanf("%d", &start);
dijkstra(start);
// 输出结果
printf("起点到各点的最短距离为:\n");
for (int i = 0; i < num_vertices; i++) {
if (i == start) {
printf("%d到%d的距离为0\n", start, i);
} else if (dist[i] == INF) {
printf("%d到%d不可达\n", start, i);
} else {
printf("%d到%d的距离为%d\n", start, i, dist[i]);
}
}
return 0;
}
```
2. Floyd算法
Floyd算法是一种动态规划算法,用于求解所有点对最短路径问题,即任意两点之间的最短路径。
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 100
#define INF INT_MAX
int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES][MAX_VERTICES];
int num_vertices;
void floyd() {
// 初始化
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
dist[i][j] = graph[i][j];
}
}
// 迭代
for (int k = 0; k < num_vertices; k++) {
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
int main() {
// 输入
printf("请输入顶点数:");
scanf("%d", &num_vertices);
printf("请输入图的邻接矩阵:\n");
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
scanf("%d", &graph[i][j]);
if (graph[i][j] == -1) {
graph[i][j] = INF;
}
}
}
// 计算最短路径
floyd();
// 输出结果
printf("任意两点之间的最短距离为:\n");
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
if (dist[i][j] == INF) {
printf("%d到%d不可达\n", i, j);
} else {
printf("%d到%d的距离为%d\n", i, j, dist[i][j]);
}
}
}
return 0;
}
```
以上是两种常见的最短路径算法的C语言实现,可以根据需要选择使用。