Thanks for telling more about what you're actually trying to do -- this is very helpful!
The code snippet you quoted is not self-contained, which makes it difficult to reason about it. However, the mutations of the stepCounts dictionary sometimes decrease the priority of heap members while they're contained in the heap. This is a crucial bug, because Heap is not aware of this happening. Your problem isn't really about the Comparable conformance; rather, it hangs entirely on this issue.
Decreasing the priority of a heap member sometimes requires the binary min-max heap to sink or raise the affected member along the (logical) path that includes it, to restore the min-max heap property. In order for this to happen, the heap needs to be explicitly notified of the priority change; i.e. you need a heap that provides operations to let you retrieve an existing item and update its priority. Heap doesn't implement such operations.
Trying to work around this by sneakily changing the priority of an unvisited node behind the back of the Heap is simply not going to work correctly, no matter what. Doing that is equivalent to mutating the hash value (a.k.a., the Equatable identity) of a Set member: it is a serious programming error.
Protocols like Equatable/Comparable/Hashable inherently require that the values returned by ==/</hashValue/etc. will be stable: if a and b are constant values, then the result of a == b or a < b must not ever change. (Otherwise e.g. Equatable.== will not implement a proper equivalence relation, rendering the conformance invalid.)
In the case of ElementValuePair, the result of < depends on the result of an arbitrary, user-specified closure, which makes it impossible to statically reason about the validity of its Comparable conformance. In the case of the closure used in shortestPathSources, < ends up consulting the stepCounts table, whose entries are mutated within the inner loop, sometimes resulting in heap items silently changing their minds about what their relative weights are. The ElementValuePair.< function is therefore not stable; that is to say, the ordering relation is not well-defined. This is going to lead to violations of core heap invariants, rendering the data structure useless. Garbage in, garbage out.
So the problem here isn't that it's difficult to spell the Comparable conformance: it never is, as long as you actually have a well-defined ordering relation. (If you don't have a well-defined ordering relation, then the concept of heaps does not apply -- the construct becomes meaningless.) In the case of Dijsktra's algorithm, you just need to associate your unvisited nodes with their shortest known distance, and the right way to do that is to simply wrap this pair of values in a straightforward custom struct:
struct Unvisited<Node>: Comparable {
var node: Node
var distance: Int
static func ==(left: Self, right: Self) -> Bool { left.distance == right.distance }
static func <(left: Self, right: Self) -> Bool { left.distance < right.distance }
}
This is one way to correctly model the minimum-queue of unvisited nodes in Dijkstra's algorithm. There is nothing weird or difficult about the Comparable conformance here -- implementing this type is a routine, trivial task.
Because this type is a struct, inserting one of its instances into Heap actually inserts a standalone copy of the value, whose priority value cannot possibly be changed without the cooperation of the container. This is a crucial feature, because it eliminates a whole class of errors that involve accidental uncoordinated mutations of such data -- such as the ones arising from the externally referenced priority values in ElementValuePair.<.
Unfortunately, Heap doesn't provide an operation to decrease the weight of its items after insertion, so it is simply not suitable for use in this version of Dijkstra's algorithm.
But that's not a problem! You just need to adapt the algorithm to remove the need to decrease priorities. One common way of doing that is to simply insert duplicates in these cases:
var shortestSources: [Node: Node] = [:]
var distances: [Node: Int] = [start: 0]
var unvisited: Heap<Unvisited<Foo>> = [Unvisited(node: start, distance: 0)]
while let source = unvisited.popMin() {
guard source.distance == distances[source.node] else {
continue // ignore obsolete dupe
}
let d = source.distance + 1
for destination in source.node.neighbors {
if d < distances[destination] ?? Int.max {
distances[destination] = d
shortestSources[destination] = source.node
unvisited.insert(Unvisited(node: destination, distance: d))
}
}
}
(Note: This code is just illustrating the idea; it probably isn't bug-free.)
In practice, I expect this modified algorithm to perform better than the variants that require a heap that supports decreasing the priority of a heap member.
Heap intentionally doesn't provide a way to look up arbitrary existing members in it; and without such a lookup function, there is also no way for it to allow updating their priorities. This is very much by design -- the machinery required to speed up such lookup operations (such as maintaining a lookup table) would significantly slow down the core heap operations (insert, popMin and popMax), while Heap really is designed to make those as fast as possible.
Heap is intentionally not the appropriate choice for use cases that absolutely do require looking up, updating, or removing arbitrary heap members. Luckily, Dijsktra's algorithm is not one of these use cases; but sometimes they do pop up. My plan is to cover them in a future Collections release, after 1.1. (For what it's worth, I think the name PriorityQueue would be right for this follow-up construct, in the footsteps of PR #51. Unfortunately that PR does not implement a lookup feature; it merely concentrates on implementing FIFO ordering for duplicate priorities instead, and I don't think that necessarily needs to be implemented as a first-class construct.)
The pattern I experience is that usually, when people ask for a solution to a generic problem on programming forums, the answerers feel a need to focus on a use case, as if that's what's being asked, instead of attacking the generic problem. It's quite disrespectful to everyone's timeāand it especially doesn't make sense to do that when the subject is a generic data structure. 
given that I've been using it for precisely as long as is possible for anyone outside of Appleā¦
.