We’re rewarding the question askers & reputations are being recalculated! Read more.
7

Here is the original statement in CLRS. Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$. It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush ...


6

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...


5

It means that each edge has only one weight, which is defined as a real number. So, this definition in compact form excludes many cases, for example: an edge doesn't have weight at all an edge has two (or more) weights an edge has weight as a complex number etc.


5

If $G$ is a tree, it has a unique MST whatever its weights are. The weights could be unique, all the same, anything.


3

Forget the even-length requirement for a moment and consider how something like Dijkstra's algorithm works. As the algorithm progresses, you have essentially two types of vertex: the ones for which you've already figured out the shortest path, and the ones for which you only have an upper bound (i.e., the shortest path you've seen to that vertex so far). ...


3

Yes. Here is the trick that always works: create a new source, $s_0$, and add an edge (with length 0) from $s_0$ to each of your starting vertices. Then, run any shortest-paths algorithm starting from $s_0$ to compute the distance from $s_0$ to each other vertex. Your technique for BFS is equivalent to this; but this is more general and can be used with ...


3

This is known as the $k$ most vital edges for the minimum spanning tree problem. It has been proved as NP-hard [1]. For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function [2], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie'...


2

The problem is $NP$-complete even in the unweighted case (e.g.: all edge weights are equal to $1$). Instead of looking for a maximum edge-induced, triangle-free subgraph we may equivalently consider the minimum number of edges to delete from the original graph in order to leave a triangle-free graph. This problem (and other, related problems) are ...


2

You're right that you can't (necessarily) apply the triangle inequality to the edges of the original graph, but that's not what's being discussed here. We know $h(u)$ is, by definition, the shortest path to $u$. Thus we immediately know that $w(u,v) + h(u) \geq h(v)$ because, if it wasn't true, $h(v)$ would not be the shortest path to $v$. The author is ...


2

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance. You are almost there. Let me continue your approach. Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i,...


2

Unfortunately, your problem is NP Complete, since you require that no vertex will be visited twice. Consider we had a polynomial time solution for some $k$. For clarification; given an undirected graph $G=(V,E)$ and two vertices $s,t$, we can find a shortest path from $s$ to $t$ of length $\geq k$ in polynomial time. Then, by extension we can solve in ...


2

Here is a list of algorithms might help you: RAPTOR : Is an algorithm developed by Microsoft and is not graph based. RAPTOR produce pareto optimal 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 Transfer Patterns ...


2

Another solution that doesn't require modifying the algorithm (so you can do it with an off-the-shelf implementation): Have two copies of the graph, one called even the other called odd. The idea is that when the total path-length so far is even/odd, you'll be in the even/odd graphs respectively. Then you only need to consider the start/end nodes on the ...


2

When you get a question about a DAG, the first thing to do is a topological sort. Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.


2

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$. Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$: $I(R)$, the cost of all inner paths of the ...


2

Your understanding is correct. The key point about TSP is that we are given a distance between every pair of cities. In other words, formally speaking, TSP is the problem of finding a minimum-weight Hamiltonian path/cycle on a weighted complete graph, given the weight function. This doesn't quite correspond to the standard intuition where a salesman is ...


2

You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v_i$ be the $i$-th node in topological order. Let $E_i$ be the set of edges ending in $v_i$. If $|E_i\setminus D'| = 0$ then: $$ d[v_i][0] = 0 $$ otherwise: $$ d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\...


2

I'm afraid that this idea does not work (and I actually post this question as homework to my students, the reason being that at first glance it looks sound and complete). Let $G(V, E)$ denote a graph with a cost function $c:e\in E\mapsto Z$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $e\langle v_i,...


1

We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want. Sorting ...


1

This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard. Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there ...


1

The problem that you are trying to solve is called "maximum weight independent set". It is NP-hard so not much hope for exactly solving it efficiently. There exist efficient approximation algorithms though (see e.g. this question).


1

Hint: consider cases where every weight is very large.


1

After sorting the edges, which takes $O(E \log E)$ time, Kruskal's algorithm adds the next cheapest edge which doesn't cause a cycle. The question is what data structure can be used to check if a given edge causes a cycle. At any given point during the execution of the algorithm, the set of edges chosen by the algorithm forms a forest. Initially, the ...


1

If $d$ indeed represents the length of the shortest path, we must have $$ d(v)= \begin{cases} 0, &\text{if $v=s$,}\\ \displaystyle\min_{u:(u,v)\in E}\{d(u)+w(u,v)\}, &\text{otherwise,} \end{cases} $$ where $w(u,v)$ is the weight of the edge $(u,v)$. So you can check whether $d$ satisfies this property for all $v$. It takes only linear time. If $...


1

Let $G=(V,E,w)$ be a weighted graph with $w$, a positive length (weight) function on $E$, i.e, the length of edge $(u,v)$ is $w(u, v)$. Let $d_{w,G}(u, v)$ denote the distance between vertex $u$ and $v$. $d_{w,G}$ will be written as $d_w$ or $d_G$ or $d$ if there is no ambiguity. An edge $(x,y)\in E$ is essential if $w(x,y)=d_w(x,y)$ and each path from $x$ ...


1

I think your approach works even if you did not give much details. Let's call $A$ the matrix. First you sort all pairs ($i$, $j$) with $i < j$ and $A_{ij}$ increasing. You also have initially a graph $G$ with all nodes and no edges. Then you process the pairs ($i$, $j$) one by one deciding whether to add an edge between nodes $i$ and $j$: compute $D$, ...


1

Being a DP, it smartly evaluates all possible options before deciding the final option at each stage. I think this is a misrepresentation of what DP means. Dynamic programming is basically divide-and-conquer with memoisation. For problems whose solutions have the right structure it guarantees to find the optimal solution, but it doesn't guarantee to ...


1

Yes, the path $(4,2,1,2,5)$ is not evaluated. However this is not a problem. Since we assume that the graph doesn't contain any negative cycles (this is a requirement for FW), there exists an optimal path for each pair of nodes that doesn't contain any cycles. Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated. By ...


1

Since there are just about 10 random points, the following simplest algorithm is should be fast and easy enough for your need. Generate random points $p_i$, $0\le i\le9 $ in the grid, in whichever way you prefer. Compute all Euclidean distances between each pair of points. (In fact, I believe for your purpose, the Manhattan distance should be fine as well. ...


1

The Hungarian method can be implemented in time $O(mn + n^2 \log n)$. Details are found for example in Alexander Schrijver's book on Combinatorial Optimization, Chapter 17. For a more implementation-oriented guide to this version of the algorithm, have a look in Chapter 7 of Mehlhorn and Näher's book. The running time is dominated by the time it takes to ...


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