CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Rafael Angarita
Rafael Angarita

Reputation: 787

Best way to find the most costly path in graph

I have a directed acyclic graph on which every vertex has a weight >= 0. There is a vertex who is the "start" of the graph and another vertex who is the "end" of the graph. The idea is to find the path from the start to the end whose sum of the weights of the vertices is the greater. For example, I have the next graph:

I(0) -> V1(3) -> F(0)
I(0) -> V1(3) -> V2(1) -> F(0)
I(0) -> V3(0.5) -> V2(1) -> F(0)

The most costly path would be I(0) -> V1(3) -> V2(1) -> F(0), which cost is 4.

Right now, I am using BFS to just enumerate every path from I to F as in the example above, and then, I choose the one with the greatest sum. I am afraid this method can be really naive.

Is there a better algorithm to do this? Can this problem be reduced to another one?

Upvotes: 6

Views: 5785

Answers (3)

Alexandru Darie
Alexandru Darie

Reputation: 61

You can perform a topological sort, then iterate through the list of vertices returned by the topological sort, from the start vertex to the end vertex and compute the costs. For each directed edge of the current vertex check if you can improve the cost of destination vertex, then move to the next one. At the end cost[end_vertex] will contain the result.

class grph:
    def __init__(self):
        self.no_nodes = 0
        self.a = []

    def build(self, path):

        file = open(path, "r")
        package = file.readline()
        self.no_nodes = int(package[0])

        self.a = []
        for i in range(self.no_nodes):
            self.a.append([10000] * self.no_nodes)

        for line in file:
            package = line.split(' ')
            source = int(package[0])
            target = int(package[1])
            cost = int(package[2])

            self.a[source][target] = cost

        file.close()


def tarjan(graph):
    visited = [0] * graph.no_nodes
    path = []

    for i in range(graph.no_nodes):
        if visited[i] == 0:
            if not dfs(graph, visited, path, i):
                return []
    return path[::-1]


def dfs(graph, visited, path, start):
    visited[start] = 1
    for i in range(graph.no_nodes):
        if graph.a[start][i] != 10000:
            if visited[i] == 1:
                return False
            elif visited[i] == 0:
                visited[i] = 1
                if not dfs(graph, visited, path, i):
                    return False
    visited[start] = 2
    path.append(start)
    return True


def lw(graph, start, end):

    topological_sort = tarjan(graph)
    costs = [0] * graph.no_nodes

    i = 0
    while i < len(topological_sort) and topological_sort[i] != start:
        i += 1

    while i < len(topological_sort) and topological_sort[i] != end:

        vertex = topological_sort[i]

        for destination in range(graph.no_nodes):

            if graph.a[vertex][destination] != 10000:

                new_cost = costs[vertex] + graph.a[vertex][destination]
                if new_cost > costs[destination]:
                    costs[destination] = new_cost

        i += 1

    return costs[end]

Input file:

6
0 1 6
1 2 2
3 0 10
1 4 4
2 5 9
4 2 2
0 2 10

Upvotes: 3

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

Since your graph has no cycles* , you can negate the weights of your edges, and run Bellman-Ford's algorithm.

* Shortest path algorithms such as Floyd-Warshall and Bellman-Ford do not work on graphs with negative cycles, because you can build a path of arbitrarily small weight by staying in a negative cycle.

Upvotes: 4

zw324
zw324

Reputation: 27180

In general longest path problem is NP-hard, but since the graph is a DAG, it can be solved by first negating the weights then do a shortest path. See here.

Because the weights reside on the vertices, before computing, you might want to move the weights to the in edges of the vertices.

Upvotes: 2

Related Questions