рассчитать следующий кратчайший путь (минимальный переход к месту назначения)

здесь структура для вычисления кратчайшего пути (прыжка) с помощью Dijkstra по omnet.

void cTopology::calculateUnweightedSingleShortestPathsTo(Node * _target) {
// multiple paths not supported :-(
if (!_target) throw cRuntimeError(this, "..ShortestPathTo(): target node is NULL");
target = _target;
for (int i = 0; i < num_nodes; i++) {
nodev[i].known = false; // not really needed for unweighted
nodev[i].dist = INFINITY;
nodev[i].out_path = NULL;
}
target - > dist = 0;
std::deque < Node * > q;
q.push_back(target);
while (!q.empty()) {
Node * v = q.front();
q.pop_front();
// for each w adjacent to v...
for (int i = 0; i < v - > num_in_links; i++) {
if (!(v - > in_links[i] - > enabl)) continue;
Node * w = v - > in_links[i] - > src_node;
if (!w - > enabl) continue;
if (w - > dist == INFINITY) {
w - > dist = v - > dist + 1;
w - > out_path = v - > in_links[i];
q.push_back(w);
}
}
}
}

Я хотел найти и записать следующий кратчайший прыжок. Может ли кто-нибудь помочь мне в этом вопросе? теоретически, мне нужно создать одну новую структуру, которая рассчитывает кратчайший путь без ранее выбранного следующего узла правильно?

0

Решение

чтобы было проще ..
ты можешь использовать …

родитель []

хранить данные / идентификатор в предыдущем узле.

затем, чтобы получить путь, вам просто нужно изменить его ..

parent [parent [parent [цель]] -> родитель [родитель [цель] -> родитель [цель]

код, вы можете увидеть здесь …

http://pastebin.com/YUBicFjy 
0

Другие решения


По вопросам рекламы [email protected]