## A shortest trail problem

I am currently learning stuff about networks and I saw this shortest trail problem given in the book, yet left with no answers and I have no idea about. Say have a graph $$G(V,E)$$ as a directed graph with a distinguished source node $$s$$ and sink node $$t$$. For every edge $$e\in E$$ has a possibly negative length $$l(e)$$. show that a shortest trail(a walk without repeating edges) from $$s$$ to $$t$$ can be found in polynomial time

## Remove a vertex from a graph keeping shortest path distance same

How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices?

## Does DFS in an unweighted DAG find the shortest path for each vertex from a source?

I have many questions which related to this topic. I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths of all vertex by asking about each vertex whether it’s weighted higher than edge plus previous vertex. The point is, I don’t understand since we are in DAG why isn’t DFS alone enough to find shortest paths. Both weighted and unweighted. I also don’t understand why we need a stack in topological sort. If you were to perform a DFS on some DAG. It will automatically produce a topological sort, if you do a pre-order DFS traverse.

## Schedule each entree so that all entrees are completed in the shortest amount of time

Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree E_i, takes c_i time to cook and d_i time to “dress up”. The dressing up of entrees can occur while other entrees are being cooked and dressed up, but we can only cook one entree at a time. How would you go about creating an algorithm to schedule each entree E_i in a manner that they all get finished in the shortest amount of time?

## 100 row numbers to find the shortest path

I got a question that I have 100 rows of the number, as in the picture that continuous to 100 rows. There is a sequence by starting from the top, and then for each integer walk to the left or right value in the row beneath. That is if we start from the top, then 40 can only be followed by 95 or 55, 95 can only be followed by 72 or 86 and so on. And I need to find the shortest path from the top to the bottom(from the first row to 100 rows). I am thinking of plotting a graph from number 1 to 5050(cause there are in total 5050 numbers.) But how can I put weight on it later on? If I calculate weights one by one that will take ages… Is there an easier way to figure this out?

Thank you very much.

## Shortest distance in unweighted graph with two connected components

Suppose you are given an undirected graph G in which there are two components connected by a single edge. For each pair of vertices in any of the components (in same component) of G they lie on at least one simple cycle.

Given such a graph G and a pair of vertices I have to write a program which finds the shortest distance between them. The running time should be O ( V +E + q ) where q is the no of such distance queries.

Graph is unweighted so required distance should be the number of edges between the vertices .

If I use BFS for each query then I will not be able to do it in required time .

I think I will have to use articulation points somehow .

## Finding shortest path in directed graph

Suppose you are on a road trip driving from point A to point B. There are several scenic routes you would like to drive through but they are time-consuming so you only want to drive through exactly one. Design a reasonably efficient algorithm that, given a directed graph G = (V, E), a subset S ⊆ E, a starting vertex A and an ending vertex B, will determine if there exists a path from A to B that goes through exactly one edge in S. (reasonably efficient correct algorithm (with correctness proof), Time analysis, The efficiency of your algorithm)

## C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments.

The algorithm iterates over every edge in the graph.

For each edge it (1) finds the shortest path from the input node of the graph to the source node of the edge (Task 1).

It then (2) finds the shortest path from the sink node of the edge to output node of the graph (Task 2).

Doing this process for every edge is what is causing it to be slow.

I am currently using dijkstra’s algorithm implemented with using priority queues in C++ to find the shorest paths. According to this website the complexity of this is O(ELogV)).

There are a couple of ways that I think I could improve this.

1. There is a lot of redundant calculation going on. Once I’ve found the shortest path from a node to the output for example (Task 2), I know the shortest path for every node along the path from the node where I started. I am wondering what is an efficient way to implement this, which C++ STL containers to use? Is there anyway to estimate the decrease in complexity?

2. A different approach would be to use Floyd Warshall Algorithm which finds the shortest distances between every pair of vertices in a DAG. The complexity of this is O(V^3). Would it then be quicker to look this information up when computing the shortest paths? How could I quantify how much faster this approach is.

## Shortest lifespan intelligent race ever published?

I’m looking for the published intelligent race (INT 3+) with the shortest lifespan. No need to be a playable race. Any edition will do, but 3.5 is preferable. Hoping for something with a lifespan of weeks.

I intend to run this in 3.5, but don’t mind porting. My plan is to make a short-lived race’s settlement around a Photostatic Rock deposit (an underdark feature that memorizes event around it) and use it as a form of ‘cultural memory’.

I need natural lifespans, so no summons. First party strongly preferred.

## Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $$n$$ as the number of vertices, that the number of edges is $$m=O(n)$$. From every vertex, the one outgoing edge is already labelled as “type A” (a, in short) and the other one as “type B” (b, in short).

Considering that all edges have the same cost of 1, and that the type of edge is important for the path, I would like to find the shortest path from a specific vertex $$u_1$$ to some vertex of the set $$\{v_1, …, v_k \}$$ (it is not specified which one, let’s say that in the output of the algorithm it is $$v_i$$), such that if the same type of edges in that path is followed beginning from a specific vertex $$u_2$$, then that second path would also conclude to some vertex $$v_j$$ of the aforementioned set $$\{v_1, …, v_k \}$$. This means that in some instance it could possibly hold that $$i\neq j$$, or in some other $$i=j$$.

The output of the algorithm it would be nice to have, therefore, can be said to be the sequence of edge types of path (e.g.: aababb), and the vertices $$v_i$$ and $$v_j$$. The input, of course, is the graph, the vertices $$u_1$$ and $$u_2$$, and the set of vertices $$\{v_1, …, v_k \}$$.

There can be many solutions to this problem, so let’s say we would want the one giving the lexicographically smallest sequence of edge types (i.e. $$abab < abba$$) on the paths.

Currently, what I have thought of is a version of two simultaneous BFS traversals, from $$u_1$$ and $$u_2$$ correspondingly, each with its own queue and parent-set, by following the same types of edges on each step (the lexicographical ordering on ties would be guaranteed by first queuing the vertices from a-edges and then from b-edges) and by considering “visited” every pair of vertices (i.e. $$w$$ “visited” = $$w$$ visited from $$u_1$$ and $$w$$ visited from $$u_2$$ = parent-set entries for $$w$$ exist for both two tables of parents) that have already been explored (because it wouldn’t be correct to consider as visited the nodes of each individual instance of the BFS, since this path from $$u_1$$ possibly couldn’t in some instance guarantee that when the same edge types are followed from $$u_2$$ it would lead to some $$v_j\in\{v_1, …, v_k \}$$). This algorithm has a time complexity of $$O((m+n)^2)=O(n^2)$$, since $$m=O(n)$$.

Is there anything faster that can be applied here, considering (if it would be of any importance to the algorithm) that I can determine the adjacency of two vertices and the neighbours of a vertex in $$O(1)$$? Maybe using dynamic programming, or another graph algorithm modification that could make this faster than $$O(n^2)$$ in time complexity?