diff --git a/GraphViz-2.24-Normalize-shebangs-in-examples.patch b/GraphViz-2.24-Normalize-shebangs-in-examples.patch
new file mode 100644
index 0000000..4dd8416
--- /dev/null
+++ b/GraphViz-2.24-Normalize-shebangs-in-examples.patch
@@ -0,0 +1,37 @@
+From 51418f0513f39b471ab6d49221a6e89868aef5d1 Mon Sep 17 00:00:00 2001
+From: =?UTF-8?q?Petr=20P=C3=ADsa=C5=99?= <ppisar@redhat.com>
+Date: Thu, 7 Nov 2019 14:07:32 +0100
+Subject: [PATCH] Normalize shebangs in examples
+MIME-Version: 1.0
+Content-Type: text/plain; charset=UTF-8
+Content-Transfer-Encoding: 8bit
+
+Signed-off-by: Petr Písař <ppisar@redhat.com>
+---
+ examples/clusters2.pl  | 2 +-
+ examples/primes_aux.pl | 2 +-
+ 2 files changed, 2 insertions(+), 2 deletions(-)
+
+diff --git a/examples/clusters2.pl b/examples/clusters2.pl
+index 4a8af15..ea5ed4a 100644
+--- a/examples/clusters2.pl
++++ b/examples/clusters2.pl
+@@ -1,4 +1,4 @@
+-#!perl -w
++#!/usr/bin/perl -w
+ 
+ use strict;
+ use lib '.';
+diff --git a/examples/primes_aux.pl b/examples/primes_aux.pl
+index 2540bef..e7222de 100755
+--- a/examples/primes_aux.pl
++++ b/examples/primes_aux.pl
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/perl -w
++#!/usr/bin/perl -w
+ # badly written program in the hopes it would sound nice
+ # - Greg McCarroll
+ #
+-- 
+2.21.0
+
diff --git a/perl-GraphViz.spec b/perl-GraphViz.spec
index 9928e66..490c929 100644
--- a/perl-GraphViz.spec
+++ b/perl-GraphViz.spec
@@ -5,36 +5,34 @@ Summary:        Interface to the GraphViz graphing tool
 License:        GPL+ or Artistic
 URL:            https://metacpan.org/release/GraphViz
 Source0:        https://cpan.metacpan.org/authors/id/R/RS/RSAVAGE/GraphViz-%{version}.tgz
+# Normalize shebangs
+Patch0:         GraphViz-2.24-Normalize-shebangs-in-examples.patch
 BuildArch:      noarch
-BuildRequires:  graphviz-devel
 BuildRequires:  coreutils
 BuildRequires:  findutils
+# graphviz for the "dot" tool
+BuildRequires:  graphviz
+BuildRequires:  graphviz-devel
 BuildRequires:  make
 BuildRequires:  perl-generators
 BuildRequires:  perl-interpreter
-BuildRequires:  perl(Carp) >= 1.01
+BuildRequires:  perl(:VERSION) >= 5.6
 BuildRequires:  perl(Config)
 BuildRequires:  perl(ExtUtils::MakeMaker) >= 6.76
-BuildRequires:  perl(File::Which) >= 1.09
-BuildRequires:  perl(Getopt::Long) >= 2.34
-BuildRequires:  perl(IO::Dir) >= 1.04
-BuildRequires:  perl(IO::File) >= 1.1
+BuildRequires:  perl(strict)
+BuildRequires:  perl(warnings)
+# Run-time:
+BuildRequires:  perl(Carp) >= 1.01
 BuildRequires:  perl(IPC::Run) >= 0.6
 BuildRequires:  perl(lib)
-BuildRequires:  perl(LWP::Simple) >= 6
 BuildRequires:  perl(Parse::RecDescent) >= 1.965001
-BuildRequires:  perl(Pod::Usage) >= 1.16
-BuildRequires:  perl(strict)
-BuildRequires:  perl(Test::More) >= 1.001002
 BuildRequires:  perl(Time::HiRes) >= 1.51
 BuildRequires:  perl(vars)
-BuildRequires:  perl(warnings)
 BuildRequires:  perl(XML::Twig) >= 3.52
-BuildRequires:  perl(XML::XPath) >= 1.13
-BuildRequires:  sed
-# optional test
-BuildRequires:  perl(Test::Pod) >= 1.48
-# not autodetected
+# Tests:
+BuildRequires:  perl(File::Which) >= 1.09
+BuildRequires:  perl(Test::More) >= 1.001002
+# "dot" command is executed from GraphViz module
 Requires:       graphviz
 Requires:       perl(:MODULE_COMPAT_%(eval "`perl -V:version`"; echo $version))
 
@@ -48,8 +46,8 @@ the GraphViz project (<http://www.graphviz.org/>).
 
 %prep
 %setup -q -n GraphViz-%{version}
-find lib t -type f -exec chmod -c -x {} \;
-sed -i -e 's|#!.*perl|#!/usr/bin/perl|' examples/primes_aux.pl examples/clusters2.pl
+%patch0 -p1
+find -type f -exec chmod -x {} +
 
 %build
 perl Makefile.PL INSTALLDIRS=vendor NO_PACKLIST=1 NO_PERLLOCAL=1
@@ -71,6 +69,7 @@ make test
 %changelog
 * Thu Nov 07 2019 Petr Pisar <ppisar@redhat.com> - 2.24-11
 - Modernize a spec file
+- Correct dependencies
 
 * Fri Jul 26 2019 Fedora Release Engineering <releng@fedoraproject.org> - 2.24-10
 - Rebuilt for https://fedoraproject.org/wiki/Fedora_31_Mass_Rebuild