integration_code/solutions/dag_paths.py

"""W02: shortest paths on a DAG, allowing negative integer edge weights."""
from collections import deque


def shortest_paths(n, edges, source):
    if type(n) is not int or not 1<=n<=10000 or type(source) is not int or not 0<=source<n:
        raise ValueError("bounded valid vertices required")
    edges=list(edges)
    if len(edges)>100000:
        raise ValueError("too many edges")
    adjacent=[[] for _ in range(n)]
    incoming=[0]*n
    seen=set()
    for u,v,w in edges:
        if any(type(x) is not int for x in (u,v,w)) or not 0<=u<n or not 0<=v<n:
            raise ValueError("valid integer endpoints and weight required")
        if (u,v) in seen: raise ValueError("parallel edges excluded in this lab")
        seen.add((u,v));adjacent[u].append((v,w));incoming[v]+=1
    ready=deque(i for i in range(n) if incoming[i]==0)
    order=[]
    while ready:
        u=ready.popleft();order.append(u)
        for v,_ in adjacent[u]:
            incoming[v]-=1
            if incoming[v]==0:ready.append(v)
    if len(order)!=n:raise ValueError("graph is not acyclic")
    distance,previous=[None]*n,[None]*n
    distance[source]=0
    for u in order:
        if distance[u] is None:continue
        for v,w in adjacent[u]:
            candidate=distance[u]+w
            if distance[v] is None or candidate<distance[v]:
                distance[v]=candidate;previous[v]=u
    return distance,previous,order


def path(previous, source, target):
    if not 0<=source<len(previous) or not 0<=target<len(previous):
        raise ValueError("invalid endpoint")
    result=[];seen=set();current=target
    while current is not None:
        if current in seen:raise ValueError("invalid cyclic predecessor data")
        seen.add(current);result.append(current)
        if current==source:return list(reversed(result))
        current=previous[current]
    return None


if __name__=='__main__':
    d,p,order=shortest_paths(4,[(0,1,2),(0,2,5),(2,1,-4),(1,3,2)],0)
    print(d,order,path(p,0,3))