The Astar algorithm requires a hysteresis to be calculated. The Manhatten method, for instance, is calculated as follows:

H = 10*(abs(currentX-targetX) + abs(currentY-targetY))

Now what happens if the graph I'm running the search on is arbitrary? I.e. the nodes aren't located in a spacial dimension, and nodes can have any amount of linked nodes ranging from 0 to 100? I don't really have any way of knowing what "currentX" or "currentY" even is. The only information I have are the links between nodes; each node holds a list of the nodes it is linked with.

Am I stuck with Dijkstra’s algorithm?

The word you want is "heuristic" ;-)

In the case of an arbitrary graph, you're kind of up a creek unless you have additional data on each node that could be used to attempt to construct a heuristic, which it doesn't sound like you have.

One option is to precompute adjacency information (i.e. do a breadth-first expansion of the entire graph and store off distances between each pair of nodes in terms of number of "hops" between them) but that's pretty intensive in terms of storage use - O(n^2) in the number of nodes.

If you have the ability to preprocess the data once, before running numerous quick searches later, then you could consider assigning standard Cartesian coordinates to your nodes to enable the standard A* heuristics. Wikipedia: Graph Drawing # Layout Methods is possibly a good starting point for getting some ideas of how to do that assignment. I suspect force-directed graph drawing is the most common.

You then also have the option of doing it in as many or as few dimensions as you want. Higher dimension counts might produce more reasonable results if you tend to have very complex graphs, but will come at a higher runtime cost while doing a search. Lower dimension counts will enable faster heuristic computation, but might make it very hard to intelligently arrange the nodes. You'll either have a very costly preprocess step, or you'll end up with misleading heuristics producing expensive searches (or both). Use two dimensions only if you know that your graphs are going to be relatively simple, and map pretty naturally to a two dimensional surface.