Widest Path Problem with constraints

I was trying to develop an algorithm for widest path problem with constraints but couldn’t figure out the necessary changes required for correct output. The problem is:
Given an undirected graph with two parameters (weight,cost). We need to find the widest path from source to destination such that the cost of the path(sum of the edges of path) is within a fixed value specified by the user. In other words, it(sum of cost parameter along the path) is upper bounded by a constant value.
I modified the existing Widest Path Problem by adding and extra cost constraint while relaxing the edges but was unable to make it work for all types of graph. I was also wondering if the modified Widest Path Problem is NP-Complete. If it is not, then how should we approach it?

Determine whether given f is shortest path function

I have the following question: Let $ G = (V,E)$ be a directed graph with a weight function $ w:E\rightarrow \mathbb{R}^+$ , and let $ s \in V$ be a vertex such that there is a path from $ v$ to every other vertex, i.e $ 0\leq dist(s,v) < \infty$ . Let $ f\colon V \to \mathbb R$ a given function. Describe an algorithm that runs in $ O(|V| + |E|)$ that determines wethter this given $ f$ is the shortest path function from $ s$ , i.e $ \forall v \in V :f(v)=dist(s,v)$ .

What I thought about was to check for every $ v \in V$ whether $ f$ fulfill the two following demands:

  1. $ f(s)=0$
  2. $ f(v) \leq f(u) + w(uv)$ for all $ u \in V$ and $ uv \in E$

This runs in the proper complexity. I thought to prove it by showing that $ f(v) \leq dist(s,v) \land f(v) \geq dist(u,v) \Rightarrow f(v) = dist(f,v)$

I proved that $ f(v) \leq dist(s,v)$ , but I am stuck at proving that $ f(v) \geq dist(s,v)$ .

Navmesh awkward path generation with string pulling due to “inner” vertices

I’ve identified a problem and a possible solution related to navmesh-based pathfinding. Before diving in, I’ll preface my post with some questions to keep in mind as you read:

  • Is this a known problem that people have solved before?
  • Is there a term for the problem that could help me search for information related to it?
  • Is the solution I came up with an existing idea? If so is there a name for the algorithm or some other search term I could use to find more information?
  • Is there a better solution? If so, please point me to it.

For reference, I’m using images from http://jceipek.com/Olin-Coding-Tutorials/pathing.html#navigation-meshes and generally following the advice laid out there.

tl;dr of that blog post is

Decompose your walkable area into a navmesh, treating convex polygons as nodes and their borders as edges so that you can perform an A* search to get from point A to point B. To translate from “node ids” back to real points, use string-pulling.

Here’s a copy of the example space: initial example area

And an example generated path after performing string pulling: example area with a completed path from A to B

So far so good.

But I realized this approach generates an awkward path in a situation like this: awkward path

In this situation, a trio of nodes are all adjacent to each other, and so the A* will generally choose a path directly from the starting node to the ending node, despite an intuitive understanding that the agent can move in a straight line from A to B which travels through a different polygon.

I’ve been working on a solution to this problem and so far my best idea is to apply a transformation to the nav mesh. My description of this will be a little hazy as I’m making up terminology to describe the approach…

  • Define a shared edge as a line segment that is shared by two convex polygons in the navmesh. Maybe a.k.a. a “portal” for string-pulling purposes.
  • Define an inner vertex as a vertex in the navmesh for which all attached line segments are “shared edges”. The vertex in the center of the three polygons in the image above is an inner vertex.
  • Identify an inner vertex. Follow its attached shared edges to what I’ll call neighbor vertex. (possible improvement; If the neighbor vertex is also an inner vertex, recurse to its neighbors until all of the neighbors are non-inner.)
  • Remove all shared edges from the navmesh that were traversed in the previous step, forming a new polygon whose border is defined by the neighbor vertices in the previous step. Redefine the edges accordingly (I’ll hand-wave that)
  • Repeat until no inner vertices remain.

The result of this on the example above should result in this:

Transformed navmesh

And with the same A-B path from before, the string-pulling should now result in a straight line:

Transformed navmesh with fixed path planning

I believe that as long as the navmesh has no inner vertices, all paths generated with the approach described in the linked blog post should seem “natural” and not have any surprise corners in what seems like open space.

Per my questions at the beginning of this post, I’m looking for more information, e.g. has anybody else solved this problem before, is there a better way to do it, and is there even a name/term for this problem?

Could this be used to find the largest path in a graph?

Savitch’s theorem “test[s] the existence of a path from a vertex s to another vertex t that uses at most k edges”

Could this be used to find the largest path in a graph?

We know there’s a walk of length a from b to c. We can keep lowering a by 1 to find a d where there’s no walk from b to c. Now we know there’s a path of length d+1 between b and c. We can try other b and c to maximize d+1. Does this find the largest path in the graph?

What is my mistake?

Maximum sum path in a matrix

Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking a path, starting at any cell of the matrix and always moving downwards or rightwards. Additionally we also have to find the number of times that this sum is achievable.

For example:
For the matrix
1 1 1
2 2 2
3 3 3
The maximum sum is 12 and it occurs only once

Trees with duplicates and path cancellations

I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see it is as a tree. A picture is worth a thousand words enter image description here As you can see, at each layer there are many nodes that are equal. Each tree node contains an object that I simply represented as an integer. Also, between each node of the tree, there are a bunch of other objects, represented by the $ L_x$ values on the arrows; all the $ L_x$ values between the same pair of layers are equal.

In an effort to improve memory occupancy, I simplified the data structure using a linked list, like show in the image belowenter image description here

So, each node of the new list can be of two types, let’s say Simple and Aggregate. An Aggregate node contains the tree nodes, each of which may be connected to one or more other tree nodes. It also contains a label, which is not shown in the picture.

Problem

There may be cancellation on the tree depending on specific parameters of the tree node. To put it simply, if and only if two aggregate nodes have the same label, a cancellation between the inner tree nodes may happen. For example, it may happen that nodes 1 and 8 of the tree node has the same label and cancels-out: the path leading from 1 to 8 must be deleted (so both 1-4-8 and 1-6-8). However, how can I keep track of this cancellation in the new linked list?

Path with maximum coins in directed graph

I am trying to solve this question:

A game has n rooms and m tunnels between them. Each room has a certain number of coins. What is the maximum number of coins you can collect while moving through the tunnels when you can freely choose your starting and ending room?

Input

The first input line has two integers n and m: the number of rooms and tunnels. The rooms are numbered $ 1, 2, \dots, n$ .

Then, there are n integers $ k_1, k_2, \dots, k_n$ : the number of coins in each room.

Finally, there are m lines describing the tunnels. Each line has two integers a and b: there is a tunnel from room a to room b. Each tunnel is a one-way tunnel.

Output

Print one integer: the maximum number of coins you can collect.

Constraints $ 1 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5, 1 \le k_i \le 10^9 1 \le a,b \le n$

Example:

Input: 4 4 4 5 2 7 1 2 2 1 1 3 2 4  Output: 16 

I was thinking of doing a dfs but it’s unclear to me how to go about it, given the existence of cycles.

Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

The question was asked in an interview, and I’m not sure if this is the most optimized answer, but here goes-

You have an undirected acyclic graph, where each node has a non-negative value x and the edges have 0 value. You need to find a path with any number of nodes on it such that the total sum of all node values is exactly k. There are N nodes in the graph. You can start at any node.

I gave the brute-force solution for this problem, which is basically do a dis on each node until you find a valid “root” node, such that it has a path to one of the other nodes, with a total sum being k. The time complexity of this solution would be n^2, since we are doing DFS on each node.

The question was posed as a delivery problem, where you have N connected houses, each having a package of weight k, and the truck can start at any house and should follow a path, and has to pick the package from every house that is on that path. The weights should sum exactly to k.

A dwarven Path of the Ancestral Guardian, good builds/tips? [closed]

Recently I finished playing a character of mine in a long-running D&D campaign. My DM and I both decided it’d be best to leave my character behind because his story was finished and there was no reason for him to stay any longer.

The thing I’m having a problem with is creating a (level 12) barbarian. I’ve never played barbarian before but it seemed like a lot of fun to me! Path of the Ancestral Guardian especially spoke to me because the idea behind it is just so cool and I like being able to help my team whilst also doing damage and being able to soak it myself. The reason I really want to play a dwarf is that my party recently saved a group of dwarves from an erupting volcano (which turned out to be a monster), and I want to make a character who is thankful to them and wants to offer them his services in return.

Do any of you have any tips for me on creating such a character? What skills are important for me and which things are better to leave for other characters?

Here’s a list of my party members at this moment:

  • A Chronomancer Wizzard, a very smart character who focusses on utility spellcasting/crowd control and intelligence.
  • A Phoenix Sorcerer, an incredible fire-themed sorcerer who focusses on charisma and blasting our enemies to pieces
  • An Oath of Conquest Paladin, a dickhead paladin who deals amazing melee damage and also currently the tank of our team
  • A Circle of the Shepherd Druid, a weird but friendly guy who focusses on survival/healing and action economy. This guy also has an awakened bear, a totem of the bear “barbarian”. This bear is mainly focussed on protecting the druid though, so there is no need to take him into consideration.
  • A Pact of the Undying Warlock, an edgy but loveable character focussing on AoE, necrotic damage, and summonings.

Thanks a lot for your time!