A* average time complexity

Question

I'm doing research on two algorithms for my bachelor thesis: Floyd-Warshall and A* algorithm. Time complexity is an important part in comparison of both algorithms for my work. But due to heuristics in A*, there is no constant time complexity of algorithm. Only information that I've found is that in worst case time complexity can be exponentially difficult.

What is an average, and best possible time complexity of A* algorithm in normal practice?

Answer 1

first I suggest you look on A* as some kind of Dijkstra with heuristic approximation for the solution, so on the worst case your solution would be the time complexity of Dijkstra (which is O(|V|+|E|) * log|V|) in the original algorithm) so surely isn't exponential, of course if you consider that the heuristic function isn't bigger than the actual distance itself). for understanding sake you can look on my comparators of the "relax" function codes here when I implemented Dijkstra and A* on the same algorithm:

---
//this function is a comparator between the distance of two vertices, it will be used 
for the heap and the Relax function in Dijkstra 
struct minDistance {
    bool operator()(Vertex* a, Vertex * b) const {
        return (a->getDis() > b->getDis());
    }
};

//this function is a comparator between the distance of two vertices but with the 
heurstic function's value added, it will be used in AStar
struct minDistanceProx {
    bool operator()(Vertex* a, Vertex * b) const {
        return ((a->getDis() + a->getDisProx()) > (b->getDis() + b->getDisProx()));
        //notice that the relax function will only change the distance value,
        //but the heap will count the distance and the heuristic value together so the 
heap is sorted as planned!
    }
};
---

you can look at this as "the distance from this node to the solution is at least x away" this is why good approximation can be implemented as BFS on the transpose graph from the destination or the "aerial distance" if you consider the nodes as some kind of a map. for the best time complexity it will happen when your heuristic function would be the actual distance and the approximation will be 100% accurate - which will be straight route to the solution.