Дополню: в Laravel 8 удобно использовать scoped route model binding. Вместо ручной проверки в контроллере можно указать маршрут так: Route::get('/{category:slug}/{company:slug}', [CompanyController::class, 'show']). Тогда в методе контроллера нужно принимать аргументы Category $category, Company $company, и Laravel сам найдёт компанию, которая принадлежит этой категории (при условии, что в модели Company есть отношение category). Это избавит от whereHas и сделает код чище.
Также добавьте ограничения для слаг-параметров через where, например ->where('categorySlug', '[a-z0-9-]+') и ->where('companySlug', '[a-z0-9-]+'). Это предотвратит случайное совпадение с другими маршрутами, даже если они идут раньше.
При генерации ссылок в шаблонах используйте route('companies.show', ['categorySlug' => $company->category->slug, 'companySlug' => $company->slug]) — так не придётся собирать URL вручную.
Я делаю так: в web.php Route::get('/{categorySlug}/{companySlug}', [CompanyController::class, 'show']); в контроллере Company::whereSlug($companySlug)->whereHas('category', fn($q) => $q->whereSlug($categorySlug))->firstOrFail(). Только этот роут ставь в самый конец файла, чтоб другие урлы не ломало