在Floyd算法中,若图中存在顶点A、B、C、D、E,且已知从A到B的最短路径长度为3,从B到C的最短路径长度为1,从C到D的最短路径长度为2,从D到E的最短路径长度为4,从A到E的直接路径长度为15。若考虑通过B、C、D作为中间顶点,从A到E的最短路径长度应为多少?
答案解析
根据Floyd算法的基本思想,若存在从A到B的最短路径长度为3,从B到C的最短路径长度为1,从C到D的最短路径长度为2,从D到E的最短路径长度为4,则通过B、C、D作为中间顶点,从A到E的路径长度为3+1+2+4=10。与直接从A到E的路径长度15相比,10更短,因此从A到E的最短路径长度应为10。选项A错误,因为它只考虑了从A到B、从B到C和从C到D的路径长度;选项C错误,因为它错误地将从A到B、从B到C、从C到D和从D到E的路径长度相加;选项D错误,因为它只考虑了直接从A到E的路径长度。
正确答案:B