Is it sufficient to check if next starts with /, ie a relative link
No, it's not sufficient. Take this script as an example:
<?php header('Location: ' . $_GET['next']); ?>
An attacker could trigger an open redirect via redirect.php?next=//example.com/. You browser interprets this as an absolute URL using the same protocol.
should I try to check if its a valid path in my application?
That would be the most secure solution. If checking valid paths is not an option, you should instead make sure the URL starts with /[a-zA-Z0-9] (that is one slash and one alphanumeric character).
Checking that it starts with / and not with //, as suggested by @BenoitEsnard, might be secure in some contexts but it's not always sufficient. Take this example (and ignore the obvious XSS problem for argument's sake):
<meta http-equiv="refresh" content="0; url=<?php echo $_GET['next']; ?>">
Here, an attacker could achieve a redirect via redirect.php?next=/%26sol;example.com/ which HTML-encodes the second / and wouldn't be picked up by a filter that checks for a // beginning.
The OWASP cheat sheet on unvalidated redirects has some additional advice.