#include <iostream>
#include <vector>
using namespace std;
#define INFINITY 1000
class CEdge {
public:
CEdge() : begin(0), end(0), weight(0), used(false) {}
~CEdge() {}
int begin;
int end;
int weight;
bool used;
};
class CVerticle {
public:
CVerticle() : metrics(0) {edges.resize(0);}
~CVerticle() {edges.resize(0);}
vector<int> edges;
int metrics;
};
vector<CVerticle> verticles(0);
vector<CEdge> edges(0);
void dfs(int index) {
int i = 0;
int next_index = 0;
for (i = 0; i < verticles[index].edges.size(); i++) {
next_index = (index == edges[verticles[index].edges].begin) ? edges[verticles[index].edges].end : edges[verticles[index].edges].begin;
if (edges[verticles[index].edges].used) continue;
if (verticles[index].metrics + edges[verticles[index].edges].weight < verticles[next_index].metrics)
verticles[next_index].metrics = verticles[index].metrics + edges[verticles[index].edges].weight;
edges[verticles[index].edges].used = true;
dfs(next_index);
}
}
int main(void) {
int i = 0;
int verticlesNum = 0, edgesNum = 0;
int begin = 0, end = 0;
cout << "Number of verticles: ";
cin >> verticlesNum;
cout << "Number of edges: ";
cin >> edgesNum;
verticles.resize(verticlesNum);
edges.resize(edgesNum);
cout << "Enter " << edgesNum << " edges in format [begin] [end] [weight]:" << endl;
for (i = 0; i < edgesNum; i++) {
cin >> edges.begin;
cin >> edges.end;
cin >> edges.weight;
verticles[edges.begin].edges.push_back(i);
verticles[edges.end].edges.push_back(i);
}
cout << "Enter the first verticle of the path: ";
cin >> begin;
cout << "Enter the last verticle of the path: ";
cin >> end;
for (i = 0; i < verticles.size(); i++)
verticles.metrics = (i == begin) ? 0 : INFINITY;
dfs(begin);
cout << verticles[end].metrics << endl;
return 0;
}
орграф на Borland С++
Нужно с использованием рекурсии.
Задан орграф. Известны веса рёбер. Найти путь из i в j с min суммой весов рёбер.
Спасибо.
Алгоритм Дейкстры с обходом графа в глубину. Вернусь домой - напишу, если до меня никто не отпишется.
Алгоритм Дейкстры смотрела, но через рекурсию не нашла.
Код:
Скорее всего, можно еще оптимизировать, но суть описал.
verticles - массив вершин графа, edges - массив ребер, begin - начальная вершина, end - конечная вершина. Чтобы превратить это в орграф, достаточно при переходе от вершины к вершине проверять не только наличие ребра между ними, а и направление перехода.
P.S. Если поймаете ошибку в вычислениях - подправим. Говорю честно, писал сравнительно быстро.
спасибо, а для ориентированного?
[QUOTE=Alexander92]
Чтобы превратить это в орграф, достаточно при переходе от вершины к вершине проверять не только наличие ребра между ними, а и направление перехода.
[/QUOTE]
Ой, спасибо,не заметила.