Are new graph algorithms still being devised?

All the time! Often you'll need to come up with a modification or variant of a textbook algorithm for particular applications.

For example, node-based editors in game engines and other media software need a few key algorithms, but the ordering of incoming/outgoing edges have meaningful semantics that might need to be considered.

You may need to use a custom algorithm to write a solver for a particular problem, for example latency/delay compensation in various networks (audio, distributed sensors, etc).

Other times you may want to combine multiple algorithms into single traversals, which is often used in single-pass compilers or parsers. These can be tricky if the traversal modifies the graph.

Then there are hypergraphs, which are so generic you probably need to treat your application as a special case.

I wrote a paper detailing one last month, and conjectured that a different approach would work as well. I believe that other researchers are close to proving my conjecture. So yes.

adding to what others said: graph based neural networks is a hot topic and I believe is the next major breakthroughs in AI.