Hot answers tagged

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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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://...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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', ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 924

Only top scored, non community-wiki answers of a minimum length are eligible