Как найти самый длинный путь в графе - Исправление недочетов и поиск решений вместе с Examum.ru

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.
Note: Length of a directed path is the number of edges in it.
Examples:

Input: N = 4, M = 5

Output: 3
The directed path 1->3->2->4
Input: N = 5, M = 8

Output: 3

Simple Approach: A naive approach is to calculate the length of the longest path from every node using DFS.
The time complexity of this approach is O(N²).
Efficient Approach: An efficient approach is to use Dynamic Programming and DFS together to find the longest path in the Graph.
Let dp[i] be the length of the longest path starting from the node i. Initially all positions of dp will be 0. We can call the DFS function from every node and traverse for all its children. The recursive formula will be:

dp[node] = max(dp[node], 1 + max(dp[child1], dp[child2], dp[child3]..))

At the end check for the maximum value in dp[] array, which will be the longest path in the DAG.
Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void dfs(int node, vector<int> adj[], int dp[], bool vis[])

{

vis[node] = true;

for (int i = 0; i < adj[node].size(); i++) {

if (!vis[adj[node][i]])

dfs(adj[node][i], adj, dp, vis);

dp[node] = max(dp[node], 1 + dp[adj[node][i]]);

}

void addEdge(vector<int> adj[], int u, int v)

{

adj[u].push_back(v);

}

int findLongestPath(vector<int> adj[], int n)

{

int dp[n + 1];

memset(dp, 0, sizeof dp);

bool vis[n + 1];

memset(vis, false, sizeof vis);

for (int i = 1; i <= n; i++) {

if (!vis[i])

dfs(i, adj, dp, vis);

}

int ans = 0;

for (int i = 1; i <= n; i++) {

ans = max(ans, dp[i]);

}

return ans;

}

int main()

{

int n = 5;

vector<int> adj[n + 1];

addEdge(adj, 1, 2);

addEdge(adj, 1, 3);

addEdge(adj, 3, 2);

addEdge(adj, 2, 4);

addEdge(adj, 3, 4);

cout << findLongestPath(adj, n);

return 0;

}

Java

import java.util.ArrayList;

class Graph

{

int vertices;

ArrayList<Integer> edge[];

Graph(int vertices)

{

this.vertices = vertices;

edge = new ArrayList[vertices+1];

for (int i = 0; i <= vertices; i++)

{

edge[i] = new ArrayList<>();

}

void addEdge(int a,int b)

{

edge[a].add(b);

}

void dfs(int node, ArrayList<Integer> adj[], int dp[],

boolean visited[])

{

visited[node] = true;

for (int i = 0; i < adj[node].size(); i++)

{

if (!visited[adj[node].get(i)])

dfs(adj[node].get(i), adj, dp, visited);

dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);

}

int findLongestPath( int n)

{

ArrayList<Integer> adj[] = edge;

int[] dp = new int[n+1];

boolean[] visited = new boolean[n + 1];

for (int i = 1; i <= n; i++)

{

if (!visited[i])

dfs(i, adj, dp, visited);

}

int ans = 0;

for (int i = 1; i <= n; i++)

{

ans = Math.max(ans, dp[i]);

}

return ans;

}

public class Main

{

public static void main(String[] args)

{

int n = 5;

Graph graph = new Graph(n);

graph.addEdge( 1, 2);

graph.addEdge( 1, 3);

graph.addEdge( 3, 2);

graph.addEdge( 2, 4);

graph.addEdge( 3, 4);

graph.findLongestPath(n);

System.out.println( graph.findLongestPath( n));

}

Python3

def dfs(node, adj, dp, vis):

vis[node] = True

for i in range(0, len(adj[node])):

if not vis[adj[node][i]]:

dfs(adj[node][i], adj, dp, vis)

dp[node] = max(dp[node], 1 + dp[adj[node][i]])

def addEdge(adj, u, v):

adj[u].append(v)

def findLongestPath(adj, n):

dp = [0] * (n + 1)

vis = [False] * (n + 1)

for i in range(1, n + 1):

if not vis[i]:

dfs(i, adj, dp, vis)

ans = 0

for i in range(1, n + 1):

ans = max(ans, dp[i])

return ans

if __name__ == "__main__":

n = 5

adj = [[] for i in range(n + 1)]

addEdge(adj, 1, 2)

addEdge(adj, 1, 3)

addEdge(adj, 3, 2)

addEdge(adj, 2, 4)

addEdge(adj, 3, 4)

print(findLongestPath(adj, n))

C#

using System;

using System.Collections.Generic;

class Graph

{

public int vertices;

public List<int> []edge;

public Graph(int vertices)

{

this.vertices = vertices;

edge = new List<int>[vertices + 1];

for (int i = 0; i <= vertices; i++)

{

edge[i] = new List<int>();

}

public void addEdge(int a, int b)

{

edge[a].Add(b);

}

public void dfs(int node, List<int> []adj,

int []dp, Boolean []visited)

{

visited[node] = true;

for (int i = 0; i < adj[node].Count; i++)

{

if (!visited[adj[node][i]])

dfs(adj[node][i], adj, dp, visited);

dp[node] = Math.Max(dp[node], 1 +

dp[adj[node][i]]);

}

public int findLongestPath( int n)

{

List<int> []adj = edge;

int[] dp = new int[n + 1];

Boolean[] visited = new Boolean[n + 1];

for (int i = 1; i <= n; i++)

{

if (!visited[i])

dfs(i, adj, dp, visited);

}

int ans = 0;

for (int i = 1; i <= n; i++)

{

ans = Math.Max(ans, dp[i]);

}

return ans;

}

class GFG

{

public static void Main(String[] args)

{

int n = 5;

Graph graph = new Graph(n);

graph.addEdge( 1, 2);

graph.addEdge( 1, 3);

graph.addEdge( 3, 2);

graph.addEdge( 2, 4);

graph.addEdge( 3, 4);

graph.findLongestPath(n);

Console.WriteLine(graph.findLongestPath(n));

}

Javascript

<script>

function dfs(node, adj, dp, vis)

{

vis[node] = true;

for (var i = 0; i < adj[node].length; i++) {

if (!vis[adj[node][i]])

dfs(adj[node][i], adj, dp, vis);

dp[node] = Math.max(dp[node], 1 + dp[adj[node][i]]);

}

function addEdge(adj, u, v)

{

adj[u].push(v);

}

function findLongestPath(adj, n)

{

var dp = Array(n+1).fill(0);

var vis = Array(n+1).fill(false);

for (var i = 1; i <= n; i++) {

if (!vis[i])

dfs(i, adj, dp, vis);

}

var ans = 0;

for (var i = 1; i <= n; i++) {

ans = Math.max(ans, dp[i]);

}

return ans;

}

var n = 5;

var adj = Array.from(Array(n+1), ()=>Array());

addEdge(adj, 1, 2);

addEdge(adj, 1, 3);

addEdge(adj, 3, 2);

addEdge(adj, 2, 4);

addEdge(adj, 3, 4);

document.write( findLongestPath(adj, n));

</script>

Time Complexity: O(N+M)
Auxiliary Space: O(N)

?list=PLqM7alHXFySEaZgcg7uRYJFBnYMLti-nh

Last Updated :
30 Dec, 2021

Like Article

Save Article

Vote for difficulty

Current difficulty :
Hard

Источник

You can use a defaultdict to create your «Graph» from your list of edges/paths:

edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]

G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

print G.items()

Output:

[
  ('1', ['2', '11']), 
  ('11', ['1', '4']), 
  ('2', ['1', '4']), 
  ('4', ['2', '11'])
]

Note that I added the edges in both directions, since you’re working with an undirected graph. So with the edge (a,b), G[a] will include b and G[b] will include a.

From this, you can use an algorithm like depth-first search or breadth-first search to discover all the paths in the graph.

In the following code, I used DFS:

def DFS(G,v,seen=None,path=None):
    if seen is None: seen = []
    if path is None: path = [v]

    seen.append(v)

    paths = []
    for t in G[v]:
        if t not in seen:
            t_path = path + [t]
            paths.append(tuple(t_path))
            paths.extend(DFS(G, t, seen[:], t_path))
    return paths

Which you can use with:

G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

print DFS(G, '1')

Output:

[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')]

So the full code, with the final bit that shows the longest path:

from collections import defaultdict

def DFS(G,v,seen=None,path=None):
    if seen is None: seen = []
    if path is None: path = [v]

    seen.append(v)

    paths = []
    for t in G[v]:
        if t not in seen:
            t_path = path + [t]
            paths.append(tuple(t_path))
            paths.extend(DFS(G, t, seen[:], t_path))
    return paths


# Define graph by edges
edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]

# Build graph dictionary
G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

# Run DFS, compute metrics
all_paths = DFS(G, '1')
max_len   = max(len(p) for p in all_paths)
max_paths = [p for p in all_paths if len(p) == max_len]

# Output
print("All Paths:")
print(all_paths)
print("Longest Paths:")
for p in max_paths: print("  ", p)
print("Longest Path Length:")
print(max_len)

Output:

All Paths:
   [('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')]
Longest Paths:
   ('1', '2', '4', '11')
   ('1', '11', '4', '2')
Longest Path Length:
   4

Note, the «starting point» of your search is specified by the second argument to the DFS function, in this case, it’s '1'.

Update: As discussed in the comments the above code assumes you have a starting point in mind (specifically the code uses the node labelled '1').

A more general method, in the case that you have no such starting point, would be to perform the search starting at every node, and take the overall longest.
(Note: In reality, you could be smarter than this)

Changing the line

all_paths = DFS(G, '1')

all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]

would give you the longest path between any two points.

(This is a silly list comprehension, but it allows me to update only a single line. Put more clearly, it’s equivalent to the following:

all_paths = []
for node in set(G.keys()):
    for path in DFS(G, node):
        all_paths.append(path)

from itertools import chain
all_paths = list(chain.from_iterable(DFS(G, n) for n in set(G)))

Источник

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

// Класс для хранения ребра Graph

class Edge

{

int source, dest, weight;

public Edge(int source, int dest, int weight)

{

this.source = source;

this.dest = dest;

this.weight = weight;

}

// Класс для представления graphического объекта

class Graph

{

// Список списков для представления списка смежности

List<List<Edge>> adjList = null;

// Конструктор

Graph(List<Edge> edges, int n)

{

adjList = new ArrayList<>();

for (int i = 0; i < n; i++) {

adjList.add(new ArrayList<>());

}

// добавляем ребра в ориентированный graph

for (Edge edge: edges) {

adjList.get(edge.source).add(edge);

}

class Main

{

// Выполняем поиск в глубину на Graphе и устанавливаем время отправления всех

// вершины Graph

private static int DFS(Graph graph, int v, boolean[] discovered,

int[] departure, int time)

{

// помечаем текущий узел как обнаруженный

discovered[v] = true;

// устанавливаем время прибытия — не нужно

// time++;

// делаем для каждого ребра (v, u)

for (Edge e: graph.adjList.get(v))

{

int u = e.dest;

// если `u` еще не обнаружен

if (!discovered[u]) {

time = DFS(graph, u, discovered, departure, time);

}

// готов к возврату

// устанавливаем время отправления вершины `v`

departure[time] = v;

time++;

return time;

}

// Функция выполняет топологическую сортировку заданной DAG, а затем находит

// максимальное расстояние всех вершин от заданного источника, запустив

// один проход алгоритма Беллмана-Форда

public static void findLongestDistance(Graph graph, int source, int n)

{

// departure[] хранит номер вершины, с которой оно отправлено

// время равно его индексу

int[] departure = new int[n];

Arrays.fill(departure, —1);

// чтобы отслеживать, открыта вершина или нет

boolean[] discovered = new boolean[n];

int time = 0;

// выполняем поиск в глубину на всех неоткрытых вершинах

for (int i = 0; i < n; i++)

{

if (!discovered[i]) {

time = DFS(graph, i, discovered, departure, time);

}

int[] cost = new int[n];

Arrays.fill(cost, Integer.MAX_VALUE);

cost[source] = 0;

// Обрабатываем вершины в топологическом порядке, т.е. в порядке

// уменьшения времени их отправления в DFS

for (int i = n — 1; i >= 0; i—)

{

// для каждой вершины в топологическом порядке,

// ослабить стоимость соседних вершин

int v = departure[i];

for (Edge e: graph.adjList.get(v))

{

// ребро `e` от `v` до `u` с весом `w`

int u = e.dest;

int w = e.weight * —1; // сделать вес ребра отрицательным

// если расстояние до пункта назначения `u` можно сократить на

// получение преимущества (v, u), затем обновление стоимости до нового более низкого значения

if (cost[v] != Integer.MAX_VALUE && cost[v] + w < cost[u]) {

cost[u] = cost[v] + w;

}

// вывести самые длинные пути

for (int i = 0; i < n; i++) {

System.out.printf(«dist(%d, %d) = %2dn», source, i, cost[i] * —1);

}

public static void main(String[] args)

{

// Список ребер Graph согласно приведенной выше диаграмме

List<Edge> edges = Arrays.asList(

new Edge(0, 6, 2), new Edge(1, 2, —4), new Edge(1, 4, 1),

new Edge(1, 6, 8), new Edge(3, 0, 3), new Edge(3, 4, 5),

new Edge(5, 1, 2), new Edge(7, 0, 6), new Edge(7, 1, —1),

new Edge(7, 3, 4), new Edge(7, 5, —4)

);

// общее количество узлов в Graph (от 0 до 7)

int n = 8;

// строим graph из заданных ребер

Graph graph = new Graph(edges, n);

// исходная вершина

int source = 7;

// найти наибольшее расстояние всех вершин от заданного источника

findLongestDistance(graph, source, n);

}

Источник

Главная
Топ
Каталог
Соревнования
Тренировки
Архив
Группы
Рейтинг
Edu
API
Календарь
Помощь

CleverDoner
Блог
Команды
Попытки
Группы
Соревнования

Блог пользователя CleverDoner

Дан ориентированный граф найдите самый длинный путь . Может ли кто нибудь скинуть решения . How we find a long path in graph. Please give me solution.

8 лет назад,
#
|

+11

Либо граф цикличен и ответ INF, либо он ацикличен и тогда по нему можно запустить динамику (взять максимум ответов детей + 1)

8 лет назад,
#
^
|

Как считать динамику? Я пытался, посмотри пожалуйста мой код сверху.

8 лет назад,
#
^
|

Просто рекурсивно считать, но при этом запоминать ответ в массиве и не пересчитывать для каждой вершины ответ

8 лет назад,
#
|

Для каждой вершины i храним dp[i], где dp[i] -> длина самого длинного пути заканчивающийся в вершине i. Можно сделать это с помощью dfs-а, потому что в нем нет циклов.

Соревнования по программированию 2.0

Время на сервере: 25.05.2023 15:38:42 (k1).

Десктопная версия, переключиться на мобильную.

При поддержке

TON

Источник

1. Вспоминай формулы по каждой теме

2. Решай новые задачи каждый день

3. Вдумчиво разбирай решения

Поиск самого длинного пути в ориентированном графе

На рисунке представлена схема дорог, связывающих города A, K, I, H, G, F, B, C, E, J, D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города A в город D? Длиной пути считать количество дорог, составляющих этот путь.

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём CD т.к. из C в D выгоднее пройти через CJ-JD.

2. Зачеркнём EJ т.к. из E в J выгоднее пройти через EC-CJ.

3. Зачеркнём FC т.к. из F в C выгоднее пройти через FE-EC.

4. Зачеркнём AK, KG т.к. из A в G выгоднее пройти через AI-IH-HG.

5. Зачеркнём IF, HF т.к. из I в F выгоднее пройти через FH-HG-GF.

6. Зачеркнём AB, BC т.к. из A в C выгоднее пройти через AI-IH-HG-GF-FE-FC.

Получаем путь AI-IH-HG-GF-FE-EC-CJ-JD длиной 8.

Ответ: 8

На рисунке представлена схема дорог, связывающих города A, K, J, B, C, D, E, F, G, R, S, T, N, I, O, P, Q, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города A в город M? Длиной пути считать количество дорог, составляющих этот путь.

1. Заметим, что через середину идти совсем невыгодно, зачеркнём все дороги оттуда.

2. Также заметим дорогу LN, делающую левое направление более выгодным. Зачеркнём все дороги справа.

3. Зачеркнём OQ т.к. из O в Q выгоднее пройти через OP-PQ.

4. Зачеркнём LM т.к. из L в M выгоднее пройти через LN-NM.

Получаем путь AB-BE-EI-IO-OP-PQ-QL-LN-NM длиной 9.

Ответ: 9

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, H, I, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города A в город G? Длиной пути считать количество дорог, составляющих этот путь.

1. Зачеркнём FG т.к. из F в G выгоднее пройти через FI-IG.

2. Зачеркнём EG т.к. из E в G выгоднее пройти через EF-FI-IG.

3. Зачеркнём CF, CG т.к. из C в G выгоднее пройти через CE-EF-FI-IG.

4. Зачеркнём HI т.к. из H в I выгоднее пройти через HF-FI.

5. Зачеркнём DH, HF т.к. из D в G выгоднее пройти через DC-CE-EF-FI-IG.

Получаем путь AD-DC-CE-EF-FI-IG длиной 6.

Ответ: 6

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K, M, N, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города A в город L? Длиной пути считать количество дорог, составляющих этот путь.

1. Зачеркнём FL т.к. из F в L выгоднее пройти через FM-MN-NL.

2. Зачеркнём FM т.к. из F в M выгоднее пройти через FG-GI-IK-KM.

3. Зачеркнём KN т.к. из K в N выгоднее пройти через KM-MN.

4. Зачеркнём IJ т.к. из J в L выгоднее пройти через IK-KM-MN-NL.

5. Зачеркнём FC т.к. из A в C выгоднее пройти через AB-BC.

6. Зачеркнём GE т.к. из A в E выгоднее пройти через AB-BC-CD-DE.

Получаем 2 пути одинаковой длины 7: AB-BC-CD-DE-EH-HJ-JL и AF-FG-GI-IK-KM-MN-NL.

Ответ: 7

На рисунке представлена схема дорог, связывающих города A, F, E, C, G, I, K, M, T, L, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города A в город J? Длиной пути считать количество дорог, составляющих этот путь.

1. Зачеркнём TJ т.к. из T в J выгоднее пройти через TL-LJ.

2. Зачеркнём TL т.к. из T в L выгоднее пройти через TK-KL.

3. Зачеркнём IK т.к. из I в K выгоднее пройти через IT-TK.

4. Зачеркнём IT т.к. из I в T выгоднее пройти через IM-MT.

5. Зачеркнём IJ т.к. из I в J выгоднее пройти через IM-MT-TK-KL-LJ.

6. Зачеркнём AF т.к. из A в F выгоднее пройти через AE-EF.

7. Зачеркнём EC т.к. из E в C выгоднее пройти через EF-FC.

8. Зачеркнём AC т.к. из A в C выгоднее пройти через AE-EF-EC.

9. Зачеркнём AI т.к. из A в I выгоднее пройти через AE-EF-EC-CG-GI.

Получаем путь AE-EF-FC-CG-GI-IM-MT-TK-KL-LJ длиной 10.

Ответ: 10

На рисунке представлена схема дорог, связывающих города A, I, B, C, D, F, G, E, H, J, K, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

1. Зачеркнём KL т.к. из K в L выгоднее пройти через KJ-JL.

2. Зачеркнём HJ, HL т.к. из H в L выгоднее пройти через HK-KJ-JL.

3. Зачеркнём EH т.к. из E в H выгоднее пройти через EG-GH.

4. Зачеркнём FH т.к. из F в H выгоднее пройти через FG-GH.

5. Зачеркнём DG т.к. из D в G выгоднее пройти через DE-EG или через DF-FG.

6. Зачеркнём CE т.к. из C в E выгоднее пройти через CD-DE.

7. Зачеркнём BF т.к. из B в F выгоднее пройти через BD-DF.

8. Зачеркнём AD, AC, CD, AB т.к. из A в D выгоднее пройти через AI-IB-BD.

9. Зачеркнём EF, FI т.к. из E в I выгоднее пройти через ED-DG-GH-HI.

Получаем путь AI-IB-BD-DE-EG-GH-HK-KJ-JL длиной 9.

Ответ: 9

На рисунке представлена схема дорог, связывающих города A, B, C, E, D, H, G, F, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Какова длина самого длинного пути из города A в город K? Длиной пути считать количество дорог, составляющих этот путь.

1. Зачеркнём GJ, GK, IK т.к. из G в K выгоднее пройти через GI-IJ-JK.

2. Зачеркнём FJ т.к. из F в J выгоднее пройти через FG-GI-IJ.

3. Зачеркнём HI т.к. из H в I выгоднее пройти через HG-GI.

4. Зачеркнём DG т.к. из D в G выгоднее пройти через DF-FG или через DH-HG.

5. Зачеркнём AE т.к. из A в E выгоднее пройти через AB-BE.

6. Зачеркнём AC т.к. из A в C выгоднее пройти через AB-BC.

Теперь у нас есть много различных путей с одинаковой длиной 7. Выберем например AB-BE-EF-FG-GI-IG-GK

Ответ: 7

УСТАЛ? Просто отдохни

Источник