Shortest-Path

Problem You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi. Some edges have a weight of -1 (wi = -1), while others have a positive weight (wi > 0). Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 109] so that the shortest distance between the nodes source and destination becomes equal to an integer target. If there are multiple modifications that make the shortest distance between source and destination equal to target, any of them will be considered correct. ...

Problem A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes. ...

Problem You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on. Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board. ...

Problem You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents: A cell containing a thief if grid[r][c] = 1 An empty cell if grid[r][c] = 0 You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves. The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid. ...

Problem You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance. Return the number of good leaf node pairs in the tree. Examples Example 1: 1 / \ 2 3 \ 4 ...

Introduction The Floyd-Warshall algorithm is a classic algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It’s especially useful for dense graphs and can handle both positive and negative edge weights (though not negative cycles). Algorithm Initialization: Create a distance matrix dist where dist[i][j] is the initial weight of the edge from vertex i to vertex j, or infinity if no edge exists. Set dist[i][i] = 0 for all vertices i. Dynamic Programming Update: For each intermediate vertex k, update the distance matrix to consider paths that pass through vertex k. For each pair of vertices (i, j), compute if a shorter path exists by going through k: if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } Result: After processing all vertices, dist[i][j] will contain the shortest path distance from vertex i to vertex j. Pseudocode function floydWarshall(graph): dist = matrix of size VxV, initially filled with graph weights (or infinity if no edge exists) for each vertex v: dist[v][v] = 0 for each intermediate vertex k: for each source vertex i: for each destination vertex j: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist ...

Problem You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i]. Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability. ...

Problem There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold. Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number. ...

Open the Lock Problem Problem You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot. The lock initially starts at '0000', a string representing the state of the 4 wheels. ...