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 ...
John L.'s user avatar
  • 39k
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 ...
dkaeae's user avatar
  • 5,027
3 votes
Accepted

why use bellman-ford instead of Dijstra in RIP routing?

Bellmon Ford is used by distance vector routing protocol (DVR). In DVR technique router keep knowledge of only next router which is adjacent that's why exchange of routing database only with neighbors....
S. M.'s user avatar
  • 317
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.'s user avatar
  • 159k
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: ...
Karim H's user avatar
  • 131
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's 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 ...
Juho's user avatar
  • 22.6k
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.'s user avatar
  • 159k
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 ...
j_random_hacker's 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 ...
A. H.'s user avatar
  • 498
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, ...
Nat's user avatar
  • 1,351
1 vote

Trying to understand a Router's Forwarding Table

the router should choose the longest prefix match, or the most specific prefix that matches. so, here it will choose line 2, because of longest prefix (24 bit).
Effie's user avatar
  • 199
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 ...
Pål GD's user avatar
  • 16.1k
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 ...
Adam Cole's 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 ...
D.W.'s user avatar
  • 159k
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 ...
gnasher729's user avatar
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 ...
Algebruh's user avatar
  • 321
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.'s user avatar
  • 159k
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', ...
Discrete lizard's user avatar
  • 8,248
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, ...
Laurent Grégoire's 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 ...
vonbrand's user avatar
  • 14k

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