迪杰斯特拉算法文件读入
时间: 2024-05-26 09:09:21 浏览: 136
Dijkstra算法是一种常用的单源最短路径算法,可以用于求解一个节点到其他所有节点的最短路径。其主要思想是通过边权重不断更新起点到各个节点的距离,直到所有节点的最短距离都得到了确定。
至于文件读入,通常情况下,在使用Dijkstra算法时,需要从外部文件中读入图的信息(如节点、边及其权重等信息),通常采用文本文件的形式,每一行代表一条边,格式为:起点 结束点 权重。例如:
1 2 5
1 3 3
2 4 1
2 3 2
3 4 6
在读取文本文件时,可以使用C++中的fstream库中的ifstream类来进行文件读取操作。具体实现可以参考如下代码:
```
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
vector<vector<int>> graph;
vector<int> dis;
vector<bool> visited;
void dijkstra(int start) {
int n = graph.size();
dis[start] = 0;
for (int i = 0; i < n - 1; ++i) {
int u = -1;
for (int j = 0; j < n; ++j) {
if (!visited[j] && (u == -1 || dis[j] < dis[u])) {
u = j;
}
}
visited[u] = true;
for (int v = 0; v < n; ++v) {
if (!visited[v] && graph[u][v] != INF) {
dis[v] = min(dis[v], dis[u] + graph[u][v]);
}
}
}
}
int main() {
ifstream fin("input.txt");
int n, m;
fin >> n >> m;
graph.resize(n, vector<int>(n, INF));
dis.resize(n, INF);
visited.resize(n, false);
for (int i = 0; i < m; ++i) {
int u, v, w;
fin >> u >> v >> w;
graph[u][v] = w;
graph[v][u] = w;
}
dijkstra(0);
for (int i = 0; i < n; ++i) {
cout << "Shortest distance from vertex 0 to vertex " << i << " is " << dis[i] << endl;
}
fin.close();
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)