帮我写个用c++导入个txt用迪杰斯特拉写个算法
时间: 2024-05-11 21:16:01 浏览: 64
C++实现Dijkstra(迪杰斯特拉)算法
好的,以下是一个简单的用C语言实现Dijkstra算法的例子,实现从一个txt文件中读取图的信息。
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTEX 100
int graph[MAX_VERTEX][MAX_VERTEX];
int dist[MAX_VERTEX];
int visited[MAX_VERTEX];
int num_vertex;
int get_min_distance() {
int min_distance = INT_MAX;
int min_vertex = -1;
for (int i = 0; i < num_vertex; 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_vertex; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[start] = 0;
for (int i = 0; i < num_vertex; i++) {
int u = get_min_distance();
visited[u] = 1;
for (int v = 0; v < num_vertex; v++) {
if (graph[u][v] && !visited[v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main() {
FILE *fp;
if ((fp = fopen("graph.txt", "r")) == NULL) {
fprintf(stderr, "Can't open graph.txt file!\n");
exit(EXIT_FAILURE);
}
// 读取图的信息
fscanf(fp, "%d", &num_vertex);
for (int i = 0; i < num_vertex; i++) {
for (int j = 0; j < num_vertex; j++) {
fscanf(fp, "%d", &graph[i][j]);
}
}
// 可以从任意节点开始
int start = 0;
dijkstra(start);
// 输出最短路径
printf("Shortest distances from vertex %d:\n", start);
for (int i = 0; i < num_vertex; i++) {
printf("Vertex %d: %d\n", i, dist[i]);
}
fclose(fp);
return 0;
}
```
该代码首先从名为"graph.txt"的文件中读取图的信息,然后从任意节点开始计算最短路径,并输出到控制台上。请注意,此代码仅用于演示用途,不适用于大型图形。
阅读全文