У меня есть исходный код на C ++ для алгоритма Беллмана Форда. Он получает входной файл с узлами, ребрами, исходным узлом и узлом назначения и возвращает кратчайший путь от одного узла к другому. Тип файла:
30 150 29 30 //Vertices,Nodes,SourceNode,DestinationNode
30 25 20 // Node30 , to Node 25 , Weight 20
1 2 29
1 3 68
24 22 8
1 5 61
24 23 76
5 4 62
Итак, я хочу сделать это для чтения ввода из файла, как:
30 150 //Vertices,Nodes
30 25 20 // Node30 , to Node 25 , Weight 20
1 2 29
1 3 68
24 22 8
1 5 61
24 23 76
5 4 62
29 30 //SourceNode,DestinationNode
Вот мой исходный код:
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
#define MaxN 111111
#define INF 1000000000
using namespace std;
int n, m, s, f;
vector< pair<int, int> > adj[MaxN];
int d[MaxN];
int rear, front;
int queue[MaxN];
bool inqueue[MaxN];
void input(){
int i, u, v, w;
cin >> n >> m >> s >> f;
for (i = 1; i <= n; i++)
adj[i].clear();
for (i = 1; i <= m; i++){
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
}
void push(int v){
if (inqueue[v]) return;
front = (front + 1) % n;
queue[front] = v;
inqueue[v] = true;
}
int pop(){
rear = (rear + 1) % n;
int v = queue[rear];
inqueue[v] = false;
return v;
}
void Bellman_Ford(){
int i, u, v, w;
memset(inqueue, false, sizeof(inqueue));
for (i = 1; i <= n; i++) d[i] = INF;
d[s] = 0;
rear = 0;
front = 0;
push(s);
while (rear != front){
u = pop();
for (i = 0; i < adj[u].size(); i++){
v = adj[u][i].first;
w = adj[u][i].second;
if (d[v] > d[u] + w){
d[v] = d[u] + w;
push(v);
}
}
}if (d[f] == INF) cout << "-1" << endl; cout << d[f] << endl;
}
int main(){
freopen("net30.txt", "r", stdin);
freopen("output.txt", "w", stdout);
input();
Bellman_Ford();
}
заранее спасибо
Если вы хотите изменить свой ввод для чтения из формата ввода 2, просто внесите следующие изменения в свою функцию ввода:
void input(){
int i, u, v, w;
ifstream fin("net30.txt");
fin >> n >> m ;
for (i = 1; i <= n; i++)
adj[i].clear();
for (i = 1; i <= m; i++){
fin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
fin >> s >> f;
fin.close();
}
Однако для преобразования содержимого файла вам потребуется написать отдельную функцию для чтения содержимого файла, а затем перезаписать его в тот же файл. Эта функция сделает это:
void changeInputFileFormat(){
int i, u, v, w;
ifstream fin("net30.txt");
fin >> n >> m >> s >> f;
vector<pair<int,pair<int,int> > > edges;
for (i = 1; i <= m; i++){
fin >> u >> v >> w;
edges.push_back(make_pair(u, make_pair(v, w)));
}
fin.close();ofstream fout("net30.txt");
//for converting to format 2
fout<<n<<" "<<m<<endl;
for( int i=0; i<edges.size(); i++ ){
fout<<edges[i].first<<" "<<edges[i].second.first<<" "<<edges[i].second.second<<endl;
}
fout<<s<<" "<<f<<endl;
fout.close();
}