如何在Dijkstra中一行使用Java Stream

Question

我正在尝试实现 Dijkstra 并且也在学习流。我无法使用流实现以下代码片段。我正在尝试使用流来迭代映射，根据节点过滤键，并更新 dist 数组，所有这些都在一行中完成。

input adj=[[2,1,1],[2,3,1],[3,4,1]] 
n=4
S(Source)=2
```

    class Pair{
        int node;
        int weight;
        public Pair(int weight,int node){
            this.node=node;
            this.weight=weight;
        }
    }
    
    class Solution {
        public int dijkstra(int[][] adj, int n, int S) {
    
            int [] dist=new int[n];
            Arrays.fill(dist,(int)1e9);
            Map <Integer,List<Pair>>  dic;
            dic=new HashMap<>();
       
            for(int i=0;i<adj.length;i++){
               
               int nd=(int)adj[i][1];
               int wt=(int)adj[i][2];
               Pair p=new Pair(wt,nd);
    
                dic.computeIfAbsent((int)adj[i][0],y->new LinkedList<Pair>()).add(p);
              }
            
            PriorityQueue <Pair>pq=new PriorityQueue<>((x,y)->x.weight-y.weight);
            dist[k-1]=0;
            pq.add(new Pair(0,S));
    
           while(pq.size()>0){
    
            int dis=pq.peek().weight;
            int node=pq.peek().node;
            pq.remove();
    
    // How to implement the below code using Streams in one line
    ------------------------------------------------
    
            dic.entrySet().stream()
                .filter(e->e.getKey().equals(node))
                .filter(entry -> entry.getValue()
                .forEach(p->{
                    if(dis+p.weight<dist[p.node-1]){
                    dist[p.node-1]=dis+p.weight;
                    pq.add(new Pair(dis+p.weight,p.node));
                        }
                }));
          }   
      }
    }

```

Answer 1

您现有的代码片段正在尝试使用 Java 的 Stream API 来迭代地图并应用一系列操作。但是，您开始使用流的方式与流的预期使用方式并不完全一致。

Java 流的设计目的不是改变外部状态（如您的

dist

数组）或执行具有副作用的操作，例如向

PriorityQueue

添加元素。流最适合用于纯功能性操作 - 例如过滤、映射或收集结果。

也就是说，如果您仍然想在预期用途的范围内使用流，您可以通过重构 Dijkstra 实现中可以用功能表达的部分来实现。由于您当前的代码不仅仅执行过滤（它还更新

dist

数组并向

pq

添加元素），因此不可能在不违反这些原则的情况下在单个流操作中完成此操作。

过滤和处理邻居的流操作可能如下所示：

dic.getOrDefault(node, Collections.emptyList()).stream()
        .filter(p -> dis + p.weight < dist[p.node - 1])
        .forEach(p -> {
            dist[p.node - 1] = dis + p.weight;
            pq.add(new Pair(dis + p.weight, p.node));
        });

在上面的代码片段中，

filter

操作确保我们只处理那些可能更新

dist

数组的对。然后使用

forEach

应用更新。这假设当您从地图中获取对列表时，您已经在处理当前节点的邻居，因此您不需要按键进行额外的过滤器。

请注意，由于副作用，这仍然不是完美的“功能”，但在这种情况下仍然使用流时，它已经是我们所能得到的最接近的了。

此外，您当前的代码似乎存在问题。变量

k

已使用但未定义。我假设它应该是

S

，即源节点，如果

dist[]

中的节点索引为 0，则该节点应该减 1，这似乎就是这种情况。

这是更正和重构的片段：

class Solution {
    public int dijkstra(int[][] adj, int n, int S) {

        int[] dist = new int[n];
        Arrays.fill(dist, (int)1e9);
        Map<Integer, List<Pair>> dic = new HashMap<>();
   
        for (int[] edge : adj) {
            int src = edge[0];
            int dest = edge[1];
            int weight = edge[2];
            Pair p = new Pair(weight, dest);
            dic.computeIfAbsent(src, k -> new LinkedList<>()).add(p);
        }
        
        PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        dist[S - 1] = 0;
        pq.add(new Pair(0, S));

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            int dis = current.weight;
            int node = current.node;
    
            dic.getOrDefault(node, Collections.emptyList()).stream()
                .filter(p -> dis + p.weight < dist[p.node - 1])
                .forEach(p -> {
                    dist[p.node - 1] = dis + p.weight;
                    pq.add(new Pair(dis + p.weight, p.node));
                });
        }
        
        // Rest of your method, presumably returning the minimum distances or similar
        // For example:
        return dist; // This should be an array of distances from the source node S
    }
}

class Pair {
    int node;
    int weight;

    public Pair(int weight, int node) {
        this.node = node;
        this.weight = weight;
    }
}

确保根据您想要实现的目标从

dijkstra

方法返回适当的结果，因为如果没有明确的输出，上面的代码片段是不完整的。