Hot answers tagged

5

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 sharing the same sequence of stops forms a route. eg. for air traveling, each flight is a trip, while each airline is a route, grouping all flights flying on the ...


5

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 destination IP address resides in the same network as your machine, what it does is create a packet destined to the target IP address and forward it to its default ...


5

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 two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors. Right after the cost of link ...


3

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, and the link layer understands only MAC addresses. For instance, if you send an IP packet over Ethernet, then the packet needs to contain an Ethernet destination ...


3

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: This is a fast algorithm that doesn't need heavy preprocessing. Trip-Based Public Transit Routing: requires more preprocessing compared to CSA and RAPTOR ...


3

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 or care what the vertices, edges and weights mean: it just finds paths. Interpreting those paths is for the user.


2

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 if it doesn't improve. Vehicle routing is an optimization problem. It is likely that the simulated annealing paradigm can be applied to it, probably in many ...


2

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 and a time. For instance, if $s$ is a bus stop and $t$ is a time, then $(s,t)$ is a vertex. If we have a bus that goes from $s$ to $s'$, takes 5 minutes, and ...


2

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 eliminated if need be). There is a vertex for each variable and each clause, and additionally there are is a vertex $s$. There are $2n$ colors, one per literal, ...


2

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 instance of Hamiltonian $st$-path with all $m$ arcs having weight 1. Let $G'$ be a graph obtained from $G$ by adding a long directed path of length $C$ ...


2

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://en.wikipedia.org/wiki/K_shortest_path_routing. I'd suggest that as a natural place to start.


2

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 step $k$ (i.e., the end). We would therefore like to compute $f(0)$, as well as a set of paths realising it. Assume we have already computed $f(i+1)$. (Clearly ...


1

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 place of interest. Subdividing an edge $e = uv$ means that you create a new vertex $v_e$ with $u$ and $v$ as neighbors, and then you delete the edge $e$ from the ...


1

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 Homeomorphism as suggested in the comments of the question to make weighting the distance between the nodes and addresses more accurate.


1

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 linear programming, and then apply an off-the-shelf ILP solver to find the best solution it can within some fixed amount of time. This gets awfully ugly. You ...


1

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 router, and your router knows your computer (and the average cheap home router can handle a few dozen devices connected to it), and sends it on to your computer.


1

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 hop is counted when a packet passes through other hardware on a network, like switches, access points, and repeaters. This isn't always the case and it depends on ...


1

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 scheduling problem is to use integer linear programming, as that has been used successfully for a number of different scheduling and operations research tasks. The ...


1

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, you're optimizing for highest likelihood: What I seek to do is to infer what is most likely the intended route [...] Now you just have to figure out your ...


1

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', which are the delivery requests. We look for an assignment of tasks to workers that minimizes the time until the last worker is finished, the makespan of the ...


1

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, but they do not have to share the exact same pattern of stop sequence (and they usually don't). What the paper describes for a route is sometimes called a route ...


1

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 addresses included in 245.248.128.0/22? in 245.248.136.0/21? I think once you understand the concepts you'll find that this question is straightforward. Advice: ...


1

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. Assuming your road network is given as a graph, for every node you will want to store: The earliest time each person using public transport can get to that node For ...


1

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 your problem is quite small, you'd have to settle for approximate solutions. There are algorithms that can solve enormous instances of TSP in (somewhat) ...


1

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 information. Here's an outline of the most obvious approach that I can see: Convert the given set of routes to an adjacency matrix. Since each edge $(A,B)$ ...


1

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 enough, and only dive into the literature if ILP does not meet your needs. One formulation as ILP could go something like this. For each edge $e$ and each source $...


1

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 price you need to pay to exchange. In such case, negative weight of a route between some nodes would mean you are paid more than you pay for such a chain of ...


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