输入正文bobo老师,您在实现Dijkstra算法时,用pq存储了一个Node。我在做leetcode题目时发现,用如下更简洁的写法也ok
1 | PriorityQueue< int []> pq = new PriorityQueue<>((a, b) -> a[ 1 ] - b[ 1 ]); |
相当于用pq存储了一个维度为2的数组,其中index为0表示的是顶点,1表示的距离。用lambda表达式确定pq的排序。不知道这种写法是不是不正式?在正式面试中可以接受吗?
第2个是我自己的一个观察。在做一般的BFS时,我们用queue实现,为了避免重复入队问题,所以visited和入队操作必须写在一起。也就是说,一个点入队后,马上要设置其visited为true,否则会重复入队,有时候数据量大会超时。而Dijkstra算法因为要不断update这个distance,所以重复入队反倒是必须的。