#Offtopic: algorithm problem, find longest path between two nodes of a graph

52 messages · Page 1 of 1 (latest)

next ruin
#

this is a homework of mine, I wrote some code but it doesn't work.

s$t
###
###

this is a graph that is given to the script as input, using a matrix.
i convert this matrix to a graph with this format.

[['node_1','node_2'],['node_1,'node_3'] ...]
each item of the list represents two connected nodes.

$ means blocked, # means unblocked.
s means start and t means target/destination.

I've read an article about implementing longest path algorithm and came up with dfs.

here is my code:

from collections import defaultdict
total_lines = input()
rows = []
edges = []
for i in range(int(total_lines)):
    rows.append(input())

start = ''
end = ''

for r,row in enumerate(rows):
    for c,column in enumerate(row):
        if column == "$": continue
        this = rows[r][c]
        this_id = f"{r}-{c}"
        # print(this)
        if this == 's':
            start = this_id
        if this == 't':
            end = this_id

        if (c<len(row)-1):
            next_column = row[c+1]
            if next_column == "$":
                continue

            edges.append([f"{r}-{c}",f"{r}-{c+1}"])

        if (r<len(rows)-1):
            next_row = rows[r+1]
            if next_row[r] == "$":
                continue

            edges.append([f"{r}-{c}",f"{r+1}-{c}"])


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


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


all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]
max_len   = max(len(p) for p in all_paths)
max_paths = [p for p in all_paths if len(p) == max_len]

for p in max_paths:
    if p[0] == start and p[-1] == end:
        print(p)
#

the program finds some longest paths but it can't find the path between start and end
here is another example input

5
$ $ t # #
s # # # $
$ # # # $
$ $ # # $
# # # # $
sage current
#

longest path is hard

#

np-hard in fact

#

inverting a depth first search is not enough

#

all the algorithms I know for it involve dynamic programming as a step

#

there is one algorithm that doesn't

#

the exhaustive dfs

#

which checks every possible path

next ruin
#

so you mean I should check every unique possible path and then grab the longest one as answer?

sage current
#

yeah

#

thats the only algorithm i know that doesn't require going deep into optimization theory

next ruin
#

but i think it is already doing it

#

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

#

but it doesn't work

sage current
#

I would expect one call to dfs

#

as how you would normally implement exhaustive dfs is to just ignore the ending condition and keep going

#

basically assuming there is a wall all around the target node

next ruin
#

I don't know

#

let me send you my source

sage current
next ruin
#

wdym?

sage current
next ruin
#

yes

#

the longest one

#

I already wrote a code to convert the input matrix to a graph

#

that can please their code

sage current
#

the above stack overflow is for any path not just the ones that start and end with s and t

next ruin
#

you mean any path from anywhere to anywhere?

#

that's too generic

#

what can i do to fix it

sage current
#

exactly

#

I believe you need to call DFS once with the start node, and modify it to keep track of only paths that have made it to t

next ruin
#

can you show me code

#

i'm a bit dumb

sage current
#

Im not going to give code out for a homework problem

next ruin
#

aright

next ruin
#

but I can't see or understand your point

#

can you explain furthermore using a small snippet?

next ruin
sage current
#

so here is depth first search

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)
next ruin
#

what language is this

#

it certainly isn't rust

sage current
#

its just pseudo code

next ruin
#

the homework teacher allows others to help

#

this is just a part of their actual problem

sage current