## TL;DR

Given a number of vertices `N` and a list of weighted directed edges in a directed acyclic graph (each edge is written as `[start, end, weight]` where `from < to`), compute the weight of the shortest path from vertex `0` to vertex `N - 1`.  If there is no such path, return `-1`.

## Background

A weighted DAG is a directed acyclic graph where each edge has a weight associated with it:













1
5
3
1
5




A
B
C
D


In this example, the shortest path from A to D is given by A -> B -> D, which has a total weight of 4.

Finding shortest distances in DAGs is made easier by the fact that the nodes can be _linearized:_ they can be given an order `A1, A2, ..., An` such that edges only point forward (that is, there are no edges from `Aj` to `Ai` when `j > i`).  In the example above, the two possible linear orderings are `A, B, C, D` and `A, C, B, D.`














1

1
5
5
3





A
B
C
D


## Your Task

Given a number `N` (indicating a graph with vertices `0, 1, ..., N-1`) and a list of weighted edges `[start, end, weight]` for a DAG, where `start < end` for each edge, find the weight (a.k.a. length) of the shortest path from node `0` to node `N-1`.

For example, if the input is

```
N = 4
edgeList = [
  [0, 1, 1], [0, 2, 5], [0, 3, 5], [1, 3, 3], [2, 3, 1]
]
```

then we have the graph depicted above (with `0 = A`, `1 = B`, etc.) and the answer is `4`.

If there is no path from node `0` to node `N-1`, return `-1`.

## Notes and Warnings

**Precondition:** `N` will always be greater than 1, and edge weights will always be positive integers.  There may be multiple edges going between two nodes.

**Warning:** You will probably need to use a dynamic programming solution if you want your solution to run fast enough not to time out--that's the whole point of this kata!


However, a well-written general shortest-path algorithm such as Dijkstra's Algorithm may also be fast enough to past the soak tests.  (The reason is that the dividing line between linear and linearithmic time is hard to define and depends on a variety of external factors, so the kata's tests err on the safe side.)

Source: codewars | Difficulty: EASY
Tags: Dynamic programming

Graph algorithms

Starter code: def shortest(N, edgeList):
	

Solutions:
import heapq
from collections import defaultdict

def shortest(N, edge):
	(ver, inf) = (defaultdict(list), 10 ** 10)
	for e in edge:
		ver[e[0]].append(e[1:])
	dist = {i: inf for i in range(N)}
	(dist[0], pq) = (0, [])
	heapq.heappush(pq, [dist[0], 0])
	while pq:
		(u_dis, u_node) = heapq.heappop(pq)
		if u_dis == dist[u_node]:
			for v in ver[u_node]:
				v_node = v[0]
				v_wei = v[1]
				if dist[u_node] + v_wei < dist[v_node]:
					dist[v_node] = dist[u_node] + v_wei
					heapq.heappush(pq, [dist[v_node], v_node])
	return -1 if dist[N - 1] == inf else dist[N - 1]


def shortest(n, edges):
	m = [0] + [float('inf')] * (n - 1)
	for (start, end, weight) in sorted(edges):
		if m[start] == float('inf'):
			continue
		m[end] = min(m[start] + weight, m[end])
	return -1 if m[-1] == float('inf') else m[-1]


def shortest(N, edgeList):
	edgeList.sort(key=lambda x: x[0])
	path_values = [None for _ in range(N)]
	path_values[0] = 0
	for edge in edgeList:
		if path_values[edge[0]] != None:
			new_val = edge[2] + path_values[edge[0]]
			if path_values[edge[1]] == None:
				path_values[edge[1]] = new_val
			else:
				path_values[edge[1]] = min(path_values[edge[1]], new_val)
	if path_values[-1] == None:
		return -1
	else:
		return path_values[-1]


def shortest(N, edges):
	path = [0] + [float('inf')] * (N - 1)
	for (start, end, weight) in sorted(edges):
		if path[start] == -1:
			continue
		path[end] = min(path[start] + weight, path[end])
	return -1 if path[-1] == float('inf') else path[-1]


from collections import defaultdict
INFINITY = 2 ** 80

def shortest(N, edgeList):
	edges = defaultdict(list)
	for (fro, to, weight) in edgeList:
		edges[fro].append((to, weight))
	dist_dp = [INFINITY] * N
	dist_dp[0] = 0
	for i in range(N):
		for (to, w) in edges[i]:
			dist_dp[to] = min(dist_dp[to], dist_dp[i] + w)
	return -1 if dist_dp[N - 1] >= INFINITY else dist_dp[N - 1]


from collections import defaultdict
from heapq import heappop, heappush
from typing import List, Tuple

def shortest(N: int, edgeList: List[Tuple[int, int, int]]) -> int:
	graph = defaultdict(list)
	for (v, u, e) in edgeList:
		graph[v].append((u, e))
	pathes = defaultdict(lambda : float('inf'), {0: 0})
	queue = [(0, 0)]
	while queue:
		(cost, v) = heappop(queue)
		if v == N - 1:
			return cost
		for (u, e) in graph[v]:
			new_cost = cost + e
			if new_cost < pathes[u]:
				pathes[u] = new_cost
				heappush(queue, (new_cost, u))
	return -1


def shortest(N, es):
	ee = [[] for _ in range(N)]
	for (f, t, w) in es:
		ee[f].append((t, w))
	dd = [2139062143 for _ in range(N)]
	f = [False for _ in range(N)]
	dd[0] = 0
	q = [0]
	f[0] = True
	while len(q) > 0:
		k = q.pop()
		f[k] = False
		for (t, w) in ee[k]:
			if dd[t] > dd[k] + w:
				dd[t] = dd[k] + w
				if not f[t]:
					q.append(t)
					f[t] = True
	return -1 if dd[N - 1] == 2139062143 else dd[N - 1]


def shortest(N, edgeList):
	import math
	edgeList.sort(key=lambda x: x[0])
	path_length = [math.inf for _ in range(N)]
	path_length[0] = 0
	for (start, end, weight) in edgeList:
		if path_length[start] == math.inf:
			continue
		path_length[end] = min(path_length[start] + weight, path_length[end])
	result = path_length[N - 1]
	return result if result is not math.inf else -1


from collections import defaultdict
from heapq import *

def shortest(N, edges):
	f = 0
	t = N - 1
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen, mins) = ([(0, f, ())], set(), {f: 0})
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return cost
			for (c, v2) in g.get(v1, ()):
				if v2 in seen:
					continue
				prev = mins.get(v2, None)
				next = cost + c
				if prev is None or next < prev:
					mins[v2] = next
					heappush(q, (next, v2, path))
	return -1