Remember the design principle: "Encapsulate what changes often" or "encapsulate what varies". As the engineer, you know best what is likely to change. You wouldn't want to hard-code the year 2012 into code that will live until next decade, but you also wouldn't want to make "Math.PI" a configuration setting either--that'd be extra overhead and configuration that you'd never need to touch.
That principle doesn't change with dependency injection.
Are you writing one algorithm and you know which implementation of Set you need, like in your Dijkstra example? Create your object yourself. But what if your co-worker is soon to deliver a fantastic new implementation of Set optimized for your use-case, or what if you are experimenting with different collection implementations for benchmarking? Maybe you'll want to inject a Provider until the dust settles. That's less likely for collections, but maybe it's more likely for similar disposable objects you might think of as "helper objects".
Suppose you're choosing between different types of CreditCardAuthService that may vary at runtime. Great case for injection. But what if you've signed a five-year contract and you know your code is going to be replaced long before then? Maybe hard-coding to one service makes more sense. But then you have to write some unit tests or integration tests and you really don't want to use a real credit card backend. Back to dependency injection.
Remember: code is malleable. Someday you may decide that you need to rip out your hard-coded HashSet and replace it with something else, which is fine. Or maybe you'll discover that you need your service to vary often enough that it should be Guice-controlled, and then you add a constructor parameter and a binding and call it a day. Don't worry about it too much. Just keep in mind that just because you have a hammer, not every problem is a Provider<WoodFasteningService>
.