Дан граф как список рёбер edges и две вершины start и end. Рёбра соединяют две вершины, и расстояния между ними равны 1.
Найдите кратчайший путь от start до end. Верните путь в виде списка вершин или пустой список, если пути нет.
Пример 1:
Ввод: edges = [[1,8],[2,1],[5,1],[3,8],[3,5]], start = 2, end = 5 Вывод: [2,1,5]
Пример 2:
Ввод: edges = [[8,4],[1,2],[2,3],[1,3]], start = 2, end = 4 Вывод: []
Ограничения:
len(edges) >= 0start >= 1end >= 1using System.Collections.Generic;
public class Solution {
public static List<int> FindShorteshPath(List<List<int>> edges, int start, int end) {
// строим граф в виде списка смежности
var graph = new Dictionary<int, List<int>>();
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (!graph.ContainsKey(u)) graph[u] = new List<int>();
if (!graph.ContainsKey(v)) graph[v] = new List<int>();
graph[u].Add(v);
graph[v].Add(u);
}
var queue = new Queue<int>();
queue.Enqueue(start);
// ключ: номер посещенной вершины, значение: родительский узел
var visited = new Dictionary<int, int?>();
visited[start] = null;
// делаем обход в ширину
while (queue.Count > 0) {
int node = queue.Dequeue();
// останавливаемся, если дошли до вершины end
if (node == end) {
break;
}
foreach (var neighbor in graph[node]) {
if (!visited.ContainsKey(neighbor)) {
visited[neighbor] = node;
queue.Enqueue(neighbor);
}
}
}
// нет ни одного пути из start в end
if (!visited.ContainsKey(end)) {
return new List<int>();
}
// восстанавливаем путь от конца к началу
var path = new List<int>();
int? current = end;
while (current != null) {
path.Add(current.Value);
current = visited[current.Value];
}
// разворачиваем в правильном порядке
path.Reverse();
return path;
}
}using System.Collections.Generic;
public class Solution {
public static List<int> FindShorteshPath(List<List<int>> edges, int start, int end) {
// строим граф в виде списка смежности
var graph = new Dictionary<int, List<int>>();
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (!graph.ContainsKey(u)) graph[u] = new List<int>();
if (!graph.ContainsKey(v)) graph[v] = new List<int>();
graph[u].Add(v);
graph[v].Add(u);
}
var queue = new Queue<int>();
queue.Enqueue(start);
// ключ: номер посещенной вершины, значение: родительский узел
var visited = new Dictionary<int, int?>();
visited[start] = null;
// делаем обход в ширину
while (queue.Count > 0) {
int node = queue.Dequeue();
// останавливаемся, если дошли до вершины end
if (node == end) {
break;
}
foreach (var neighbor in graph[node]) {
if (!visited.ContainsKey(neighbor)) {
visited[neighbor] = node;
queue.Enqueue(neighbor);
}
}
}
// нет ни одного пути из start в end
if (!visited.ContainsKey(end)) {
return new List<int>();
}
// восстанавливаем путь от конца к началу
var path = new List<int>();
int? current = end;
while (current != null) {
path.Add(current.Value);
current = visited[current.Value];
}
// разворачиваем в правильном порядке
path.Reverse();
return path;
}
}package main
func findShorteshPath(edges [][]int, start int, end int) []int {
// строим граф в виде списка смежности
graph := make(map[int][]int)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
queue := []int{start}
// ключ: номер посещенной вершины, значение: родительский узел
visited := make(map[int]int)
visited[start] = -1
// делаем обход в ширину
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
// останавливаемся, если дошли до вершины end
if node == end {
break
}
for _, neighbor := range graph[node] {
if _, found := visited[neighbor]; !found {
visited[neighbor] = node
queue = append(queue, neighbor)
}
}
}
// нет ни одного пути из start в end
if _, found := visited[end]; !found {
return []int{}
}
// восстанавливаем путь от конца к началу
path := []int{}
current := end
for current != -1 {
path = append(path, current)
current = visited[current]
}
// разворачиваем в правильном порядке
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
return path
}import java.util.*;
public class Solution {
public List<Integer> findShorteshPath(List<List<Integer>> edges, Integer start, Integer end) {
// строим граф в виде списка смежности
Map<Integer, List<Integer>> graph = new HashMap<>();
for (List<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
graph.putIfAbsent(u, new ArrayList<>());
graph.putIfAbsent(v, new ArrayList<>());
graph.get(u).add(v);
graph.get(v).add(u);
}
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
// ключ: номер посещенной вершины, значение: родительский узел
Map<Integer, Integer> visited = new HashMap<>();
visited.put(start, null);
// делаем обход в ширину
while (!queue.isEmpty()) {
int node = queue.poll();
// останавливаемся, если дошли до вершины end
if (node == end) {
break;
}
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.containsKey(neighbor)) {
visited.put(neighbor, node);
queue.add(neighbor);
}
}
}
// нет ни одного пути из start в end
if (!visited.containsKey(end)) {
return new ArrayList<>();
}
// восстанавливаем путь от конца к началу
List<Integer> path = new ArrayList<>();
Integer current = end;
while (current != null) {
path.add(current);
current = visited.get(current);
}
// разворачиваем в правильном порядке
Collections.reverse(path);
return path;
}
}from collections import deque, defaultdict
from typing import *
def find_shortesh_path(edges: List[List[int]], start: int, end: int) -> List[int]:
# строим граф в виде списка смежности
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
queue = deque([start])
# ключ: номер посещенной вершины, значение: родительский узел
visited = {start: None}
# делаем обход в ширину
while queue:
node = queue.popleft()
# останавливаемся, если дошли до вершины end
if node == end:
break
for neighbor in graph[node]:
if neighbor not in visited:
visited[neighbor] = node
queue.append(neighbor)
# нет ни одного пути из start в end
if end not in visited:
return []
# восстанавливаем путь от конца к началу
path = []
current = end
while current is not None:
path.append(current)
current = visited[current]
# разворачиваем в правильном порядке
return path[::-1]/**
* @param {number[][]} edges
* @param {number} start
* @param {number} end
* @returns {number[]}
*/
export function findShorteshPath(edges, start, end) {
// строим граф в виде списка смежности
const graph = new Map();
for (const [u, v] of edges) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u).push(v);
graph.get(v).push(u);
}
const queue = [start];
// ключ: номер посещенной вершины, значение: родительский узел
const visited = new Map();
visited.set(start, null);
// делаем обход в ширину
while (queue.length > 0) {
const node = queue.shift();
// останавливаемся, если дошли до вершины end
if (node === end) {
break;
}
for (const neighbor of graph.get(node)) {
if (!visited.has(neighbor)) {
visited.set(neighbor, node);
queue.push(neighbor);
}
}
}
// нет ни одного пути из start в end
if (!visited.has(end)) {
return [];
}
// восстанавливаем путь от конца к началу
const path = [];
let current = end;
while (current !== null) {
path.push(current);
current = visited.get(current);
}
// разворачиваем в правильном порядке
return path.reverse();
}Оценка сложности
O(n), где n - размер edgesO(n)