Best way to find the most costly path in graph

Question

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?

Answer 1

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.

Answer 2

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