まず、 ワーシャルフロイド法 を用いて、任意の \(u,v\) について以下の \(d_{u,v}\)を求めます。

• \(d_{u,v} = \{\) 頂点 \(u\) から頂点 \(v\) までの最短経路の長さ \(\}\)

このとき、ペア \((i,j)\) が頂点 \(k\) の重要度に寄与する必要十分条件は以下の通りです。

• \(d_{i,j}=d_{i,k}+d_{k,j}\)
• すなわち、頂点 \(i\) から頂点 \(k\) を経由し頂点 \(j\) まで行った際の距離と、頂点 \(i\) から頂点 \(j\) までの最短経路の長さとが等しい。

ワーシャルフロイド法も、ペア \((i,j)\) が頂点 \(k\) の重要度に寄与するかの判定も、共に時間計算量 \(O(N^3)\) で行うことができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<vector<int>> g(N,vector<int>(N,1e9));
  for(int i=0;i<M;i++){
    int u,v,w;
    cin >> u >> v >> w;
    u--; v--;
    g[u][v]=min(g[u][v],w);
  }
  for(int i=0;i<N;i++){
    g[i][i]=0;
  }
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
      }
    }
  }
  vector<int> ans(N,0);
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      if(i==k){continue;}
      for(int j=0;j<N;j++){
        if(j==i || j==k){continue;}
        if(g[i][j]==g[i][k]+g[k][j]){
          ans[k]++;
        }
      }
    }
  }
  for(auto &nx : ans){cout << nx << "\n";}
  return 0;
}