讨论/技术交流/题目求助|【求助】如何用线性时间复杂度解决单源最短路径问题(详情请看原文)/
题目求助|【求助】如何用线性时间复杂度解决单源最短路径问题(详情请看原文)

题目:
Develop a linear-time (i.e., O(m + n)-time) algorithm that solves the Single Source Shortest Path problem for graphs whose edge weights are positive integers bounded by 5. (Hint. You can either modify Dijstra’s algorithm or consider
using Breath-First-Search.)

请各位大佬帮忙解答,谢谢!

3
共 13 个回复

边权受限的话可以用桶代替 dijkstra\text{dijkstra} 算法里的堆。

开一个 5n+15n+1 大小的数组作桶,一开始把起点放入 00 号桶,之后遍历桶,碰到桶里有节点,就把节点拿出来更新与这个点相邻的点的距离,更新了的节点再放入新的桶,由于 dijkstra\text{dijkstra} 算法的距离不减,因此更新的节点一定不会放到已经遍历过的桶里,复杂度 O(V+E)O(|V|+|E|),是线性的。

而且上述解法对于边权很大的情况也能用,把桶的大小从原来的全是 11 调整为按指数增长即可,这个算法叫做基数堆,时间复杂度多一个 log\log

5

我还想到了一种方式,如果a到b的边的权值是3就把b这个点拆成3个b1,b2,b3,然后每两点之间的距离是1。对于所有的边权大于1的点都进行拆点,然后跑一遍BFS。由于点最多扩大5倍,所以算法的时间复杂度保持线性。

3

这题目真不错,哪里找的?是各种魔改算法题里的一股清流。题目清晰,纯考察思想。
楼上说的很对,边权值属于[1, 5]是很关键的信息,可以从这里入手降低算法的复杂度(桶排序或者计数排序),把Dijkstra里面因为优先队列排序导致的log复杂度去掉。
具体代码我还在想。。。

2

代码我写出来了,用的是桶排序优化Dijkstra里面的堆,来降低时间复杂度。
请大佬和题主帮忙看看对不对~

public int[] dijkstraWithPqAdjacencyList(int start, List<List<int[]>> adjList) { int INF = 0x3f3f3f3f; int numOfV = adjList.size(); int[] dis = new int[numOfV]; Arrays.fill(dis, INF); boolean[] known = new boolean[numOfV]; PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1]-b[1]); for(int i=0; i<numOfV; i++) { pq.add(new int[] {i, i==start ? 0 : INF}); } while(!pq.isEmpty()) { int[] pop = pq.poll(); if(known[pop[0]]) continue; int cur = pop[0]; int d = pop[1]; known[cur] = true; dis[cur] = d; //loose for(int[] neig : adjList.get(cur)) { int neiIndex = neig[0], neiDis = neig[1]; if(!known[neiIndex] && dis[neiIndex] > d+neiDis) { dis[neiIndex] = d+neiDis; pq.add(new int[] {neiIndex, dis[neiIndex]}); } } } return dis; } public int[] dijkstraWithLinear(int start, List<List<int[]>> adjList) { int numOfV = adjList.size(); //since edge weight upper bound is 5, than (numOfV-1)*5+1 means unreachable int INF = (numOfV-1)*5+1; int[] dis = new int[numOfV]; Arrays.fill(dis, INF); boolean[] known = new boolean[numOfV]; //in dijkstra, we use priority queue //now, we use bucket sorting to get linear complexity List<Set<Integer>> buckets = new ArrayList<>(); //index means distance, node index are stored in bucket for(int i=0; i<=INF; i++) buckets.add(new HashSet<>()); //pointer of min bucket int head = 0; //init for(int i=0; i<numOfV; i++) { if(i==start) buckets.get(0).add(i); else buckets.get(INF).add(i); } //iter for(; head<=INF; head++) { Set<Integer> bucket = buckets.get(head); for(int cur : bucket) { if(known[cur]) continue; int d = head; known[cur] = true; dis[cur] = d; //loose for(int[] neig : adjList.get(cur)) { int neiIndex = neig[0], neiDis = neig[1]; if(!known[neiIndex] && dis[neiIndex] > d+neiDis) { dis[neiIndex] = d+neiDis; buckets.get(dis[neiIndex]).add(neiIndex); } } } } return dis; }
1

whose edge weights are positive integers bounded by 5.
这一句很关键,我考虑运用计数排序,将log去掉。

1

这个思路也是对的,运用到了“边权为1时的BFS自动会得到单源最短路”这个性质

和你一样的思路,代码写在下面了,可以帮忙看看有没有错误吗?谢谢大佬

感谢解答!你的描述很清晰,我懂了! 回头把算法写出来😄

感谢解答!实不相瞒,这是课上的作业😂

话说,利用线性时间复杂度排序的思路我无从下手,如果要优化掉log保证题目的linear-time,那就得用O(1)时间复杂度的来保证当前访问的节点为最优选择,实在想不出来应该怎么做...

另外,有朋友解答可以把权值>1的边分割成权值为1的边,然后用bfs解。我认为这个思路可以解决,欢迎一起讨论! 😁

了解了,谢谢!