关于A*算法和dijskra算法

关于dijskra算法和A*算法，小弟有一个疑问，希望各位大牛不惜赐教。
我知道A*算法效率要更高，可是不太明白二者在应用上有什么区别，就是什么场合应该用A*，什么场合应该用dijskra？ 对于带权图来说，怎么确定H(n)比较好呢？是不是带权图用dijskra更方便呢？还有就是不知道哪位大神有A*算法的实际应用讲解和Java实现啊，小弟**一枚，这两天看图这块有点晕。

不是有公开课　算法II　是普林斯顿的　刚开,　你快去跟

dijskra算法和A*算法本身感觉没直接的可比性吧
A*因为有估价，所以更经常被用于可行解，比如8数码
h(n)记得没错，应该是中间结点到终点的估价吧，这个只能靠经验，一般设计时复杂度不要过高
dij也有堆的实现方法，复实度O(nlgn)，类似于A*的h(n)取0

如果你只是为了以后面试的话感觉A*可以不用搞太明白。。 h的选择是一个很靠经验的问题.. 毕竟任何小于实际值的估计都能得出正确答案
A*利用heuristic避免了对一些明显差的空间的搜索 其实不仅是最短路径上 还有很多问题上A*都可以被运用

readman 发表于 2014-3-28 09:26
不是有公开课　算法II　是普林斯顿的　刚开,　你快去跟

OK,这就去，谢啦

chopper 发表于 2014-3-28 09:45
dijskra算法和A*算法本身感觉没直接的可比性吧
A*因为有估价，所以更经常被用于可行解，比如8数码
h(n)记 ...

d算法除了堆 还有实现方法?

readman 发表于 2014-3-28 11:00
d算法除了堆 还有实现方法?

有啊，只是实现上，而非算法上。
直接用double loop，O(n^2)。因为用堆的话，“每个点扩展的第一次必定最优”可能不是那么好理解，所以如果时间要求不高，就直接for for了。