Find minimum time path between two nodes
This can be done in polynomial time.

I'm assuming:


All our your nodes are charging stations.  If not, you can create a new graph that consists of only charging-stations (including start/finish) by finding the all-pairs shortest paths (or just running Dijkstra's multiple times)
The time spent charging is proportional to the distance driven.  If there are eg. paths that are shorter but require larger charges, the problem becomes much more difficult.


The optimal method will be to drive as far as you can on one charge, then fill up your battery only barely enough to make it to the next charging station.  You can do this by adding weight to each edge $\overline{AB}$ equal to the time needed to wait at $A$ while charging, taking into account the battery's initial charge.

We'll do this by altering Djikstra's algorithm.  We need to make two changes to the algorithm


In addition to giving each node a TentativeDistance, also assign it a CurrentBatteryLevel.  This will be the battery level when reaching the node, before doing any charging.  Set it to full for the initial node.
When expanding the current node and calculating the tentative distance to a neighbor-node, add to the edge-weight the amount of time that will need to be spent charging.  If there is enough charge to make it there, this will be 0, and the potential CurrentBatteryLevel for the neighbor-node will be >= 0.  If there is not, it will be the time required to charge the battery enough so that, when you make it there, CurrentBatteryLevel will be 0.


This works because we're still guaranteed to have found the shortest path to a node when expanding it.  This is true because there are no longer paths with shorter charging times, and we're only altering outgoing edges when expanding nodes (never incoming edges), so the assumptions of Dijkstra's algorithm still hold.

Also, since we only increase edge-weights, never decrease, if you have a heuristic you can still use A*.  It must consistent, since our algorithm breaks if we need to expand nodes multiple times.