Revisit DictMap usage in some places

[mtreinish]

Information

• retworkx version: main @ 9e853d4
• Python version: 3.9
• Rust version: 1.55.0
• Operating system: Linux

What is the current behavior?

Since the use of DictMap was introduced in #386 there has been a regression caused in places that used to use a HashMap for the output type. This is probably because of the additional overhead in generating an indexmap vs a hashmap. For example, looking at #489 I benchmarked dijkstra from https://github.com/mtreinish/retworkx-comparison-benchmarks with 0.10.2, main, and #489 (which we can ignore for this issue):

As you can see there for the single source case there is a noticeable regression for main vs 0.10.2. Before the 0.11.0 release I think we should revisit #386 and determine if there is a performance regression where DictMap is used and if so whether we think a deterministic iteration order is worth that extra overhead.

[IvanIsCoding]

Can you also include retworkx at the commits right after? 747a4f6

We made some other changes to Dijkstra and we bumped PyO3, I just want to narrow it down to #386

Edit: I have a feeling it is going to be https://github.com/bluss/indexmap#performance, probably something related to data to big to fit in the CPU cache

[mtreinish]

Sure, I reran the benchmarks and replaced the PR entry with 747a4f6

I think your intuition is right. It's probably because for the full USA road map networks we have too much data in the map

[mtreinish]

Now that #493 merged I think we can close this. There is probably a small regression in other places we switched to use dictmap, but we can revisit this in a follow-up where we encounter it.