5
votes
Raptor Algorithm: Differences between trip and route
Trip represents a sequence of stops plus associated arrival and departure times on each stop.
Group all trips by their sequence of stops, ignoring the time information, then each group of trips ...
- 789
5
votes
How do web browsers find out the MAC address?
So, how does the computer find out the MAC address of the server?
It doesn't. The MAC address only has validity inside a local area network (LAN), which, as the name says, is local. Unless the ...
- 4,899
5
votes
Accepted
Distance Vector Routing Example
Let us review the specification of the algorithm.
In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between ...
- 34.1k
3
votes
Accepted
Why use private IP addresses in a LAN instead of MAC address
It's not an "instead". Every packet that is sent using IP contains both a MAC address and an IP address. You need both, because the IP-layer protocol stack understands only IP addresses, ...
D.W.♦
- 141k
3
votes
Routing algorithm for train network
Here is a list of algorithms that might help you:
RAPTOR : Is an algorithm developed by Microsoft and is not graph based. RAPTOR produce pareto optimal results unlike CSA.
Connection Scan Algorithm: ...
- 131
3
votes
Bellman–Ford negative path meaning
In the context of network routing, negative-weight edges are meaningless.
Bellman–Ford is just an algorithm for finding lowest-cost paths in a weighted graph. The algorithm itself doesn't know ...
- 80.2k
2
votes
How can simulated annealing be related to the vehicle routing problem?
Simulated annealing is an optimization paradigm, in which (very roughly speaking) you start with some solution, and then try to make local changes that improve it, sometimes making a local change even ...
- 270k
2
votes
Accepted
Shortest path problem where edge weight depends on path taken
Don't do that. Instead, change the way you model the problem as a graph problem.
One crude approach: Rather than having a vertex for each bus stop, introduce one vertex for each pair of a bus stop ...
D.W.♦
- 141k
2
votes
Shortest Path using at most k colors
Here is a reduction from SAT to your problem. Let $\phi = C_1 \land \cdots \land C_m$ be a CNF on the variables $x_1,\ldots,x_n$. Consider the following graph with parallel edges (those can be easily ...
- 270k
2
votes
Accepted
Finding path with specific length in weighted graph
Your problem is NP-complete by a reduction from Hamiltonian $st$-path, even with unweighted arcs. Thus, you should not expect a polynomial-time algorithm. I'll sketch a reduction below.
Let $G$ be an ...
- 22.1k
2
votes
Raptor algorithm: find next best paths
There are standard algorithms for finding the $k$ shortest paths in a graph: you provide $k$, and it returns the shortest path, second-shortest path, ..., up to the $k$th shortest path. See https://...
D.W.♦
- 141k
2
votes
Multi-Path Length Minimization
You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems.
Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to ...
- 5,154
1
vote
Count-to-infinity avoidance techniques and hold-down timeout based question
Holddown Timer is another loop-prevention mechanism employed by distance vector routing protocol($DVR$). This feature prevents a router from learning new information about a failed route. When a ...
- 468
1
vote
Route finding on a graph that must go through multiple edges
The statement that you want a path that "goes through multiple edges" is easily replaced with a normal path finding algorithm when you observe that you can subdivide each edge containing a ...
- 13.3k
1
vote
Route finding on a graph that must go through multiple edges
I have decided that the best solution to this is a variation on Dijkstra's algorithm. Since it doesn't require a Hamiltonian Circuit and makes it easy to manage the weights. I will also use ...
- 21
1
vote
Finding stages in routing algorithm
I don't know whether there is an efficient (polynomial-time) algorithm for this problem. I wouldn't be surprised if it is NP-hard.
One approach would be to formulate this as an instance of integer ...
D.W.♦
- 141k
1
vote
How do web browsers find out the MAC address?
Your computer sends a request to your router, and the router sends it to the IP address of the server. Included in the request is your router’s IP address. So the server sends the website to your ...
- 25.2k
1
vote
In "multi hop" network, is computer => computer 0 hop or 1 hop?
As stated on this site:
A hop is a computer networking term that refers to the number of routers that a packet (a portion of data) passes through from its source to its destination. Sometimes a ...
- 279
1
vote
Accepted
Combinatorial Optimization: Shortest distance given sets of drivers and riders
These kinds of scheduling problems tend to be hard (e.g., NP-hard to solve exactly; and messy because of all of the different constraints you have).
My favorite "big hammer" for this kind of ...
D.W.♦
- 141k
1
vote
Seek to infer "correct" route from sequence of stops
To be clear, this is not an optimization problem; I do not seed to find the "best" route.
Actually this is an optimization problem! Just instead of optimizing for shortest length or fastest time, ...
- 1,331
1
vote
route and/or packing optimization algorithm
This specific problem seems to be an variation of minimizing the makespan in the job shop scheduling problem. Essentially, your couriers are modeled as 'workers' that need to process certain 'tasks', ...
- 6,978
1
vote
Raptor Algorithm: Differences between trip and route
Be careful, as the definition of route given in this paper does not seems to match the definition given in other standards (namely, GTFS). In GTFS a route is a somehow arbitrary collection of trips, ...
- 143
1
vote
How can one come up with reasonable IP subnet allocations?
Hints:
Try working out the binary representation of 245.248.136.0 (it's 32 bits) and of 245.248.128.0.
Re-read what the /21 and /22 notation means and how CIDR works.
What is the range of IP ...
D.W.♦
- 141k
1
vote
Accepted
Route planning for a car driver picking up people using public transport
A generalized version of this problem is likely $NP$-complete, however given that very few people are sharing the same car, you can probably get away with an exact, exponential time algorithm.
...
1
vote
Algorithm for finding the best “route” of tasks
If you have just one person to complete the tasks, this is the (in)famous Travelling Salesman Problem (TSP), which is NP-complete, so an efficient exact algorithm is a very remote possibility. Unless ...
- 13.6k
1
vote
Listing all possible train routes
Based on your comments, I'm assuming that if the problem asked to find all paths between $A$ and $B$ on a directed graph, you'd have no problem. So the only hurdle is how to deal with the extra route ...
- 208
1
vote
Unsplittable flow in capacitated networks
The easiest algorithm to implement will probably be to use integer linear programming, and then use an off-the-shelf ILP solver. I would suggest starting with that and seeing if it is efficient ...
D.W.♦
- 141k
1
vote
Bellman–Ford negative path meaning
It depends on the innterpretation of the graph, not the algorithm. For example, if you have a deck of cards and have a graph to represent possible exchanges, the weights of the vertices may mean the ...
- 924
Only top scored, non community-wiki answers of a minimum length are eligible