最短路径条数

求最短路径的条数

JSOI2007]重要的城市 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

int cnt[200][200];//cnt[i][j]表示i->j的最短路径的条数。
int mp[200][200];//mp[i][j]表示i->j的最短路径
//cnt[i][j]=sum(cnt[i][k]*cnt[k][j])

使用Floyd算法途中，维护cnt数组。

初始化时，若点x到点有边，则cnt[x][y]=1,即x->y一定有一条最短路径。

然后Floyd，维护cnt数组

for (int k = 1; k <= n; k++)//中间点
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (mp[i][j] > mp[i][k] + mp[k][j])
            {
				mp[i][j] = mp[i][k] + mp[k][j];
				cnt[i][j] = cnt[i][k] * cnt[k][j];
			}			
            else if (mp[i][j] == mp[i][k] + mp[k][j])
			{
				cnt[i][j] += cnt[i][k] * cnt[k][j];
			}
		}
    }
}

若cnt[i][j]=cnt[i][x]*cnt[x][j]&&mp[i][j]==mp[i][x]+mp[x][j]

则，i->j的最短路径一定经过点x