Method Dijkstra

src/linkgraph/mcf.cpp:257–305

 */
template <class Tannotation, class Tedge_iterator>
void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths)
{
	typedef std::set<Tannotation *, typename Tannotation::Comparator> AnnoSet;
	Tedge_iterator iter(this->job);
	uint16_t size = this->job.Size();
	AnnoSet annos;
	paths.resize(size, nullptr);
	for (NodeID node = 0; node < size; ++node) {
		Tannotation *anno = new Tannotation(node, node == source_node);
		anno->UpdateAnnotation();
		annos.insert(anno);
		paths[node] = anno;
	}
	while (!annos.empty()) {
		typename AnnoSet::iterator i = annos.begin();
		Tannotation *source = *i;
		annos.erase(i);
		NodeID from = source->GetNode();
		iter.SetNode(source_node, from);
		for (NodeID to = iter.Next(); to != INVALID_NODE; to = iter.Next()) {
			if (to == from) continue; // Not a real edge but a consumption sign.
			const Edge &edge = this->job[from][to];
			uint capacity = edge.base.capacity;
			if (this->max_saturation != UINT_MAX) {
				capacity *= this->max_saturation;
				capacity /= 100;
				if (capacity == 0) capacity = 1;
			}
			/* Prioritize the fastest route for passengers, mail and express cargo,
			 * and the shortest route for other classes of cargo.
			 * In-between stops are punished with a 1 tile or 1 day penalty. */
			bool express = IsCargoInClass(this->job.Cargo(), CargoClass::Passengers) ||
				IsCargoInClass(this->job.Cargo(), CargoClass::Mail) ||
				IsCargoInClass(this->job.Cargo(), CargoClass::Express);
			uint distance = DistanceMaxPlusManhattan(this->job[from].base.xy, this->job[to].base.xy) + 1;
			/* Compute a default travel time from the distance and an average speed of 1 tile/day. */
			uint time = (edge.base.TravelTime() != 0) ? edge.base.TravelTime() + Ticks::DAY_TICKS : distance * Ticks::DAY_TICKS;
			uint distance_anno = express ? time : distance;

			Tannotation *dest = static_cast<Tannotation *>(paths[to]);
			if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance_anno)) {
				annos.erase(dest);
				dest->Fork(source, capacity, capacity - edge.Flow(), distance_anno);
				dest->UpdateAnnotation();
				annos.insert(dest);
			}
		}
	}
}

/**
 * Clean up paths that lead nowhere and the root path.