使用Dijkstra算法在邻接矩阵中找到最短路径 [英] using Dijkstra algorithm to find shortest path in an adjacency matrix

问题描述

我有一个家庭作业，我应该找到两个城市之间的最便宜的机票，考虑到中途停留。

I have a homework assignment where I'm supposed to find the cheapest airfares between two cities, taking into account layovers.

我们需要与Dijkstra的算法一起使用邻接矩阵。我在看书中的算法，以及维基百科（其他网站）。我很困惑，因为在算法的参数有：

We are required to use an adjacency matrix along with Dijkstra's algorithm. I'm looking at the algorithm in my book, as well as wikipedia (among other sites). I'm confused because in the parameter for the algorithm it has:

DijkstraAlgorithm(weighted simple digraph, vertex first)

我很难理解 - 特别是当看到整个伪码时 - 为什么它只需要一个顶点作为参数？我需要找到两个顶点之间的最便宜的机票（最短路径）。为什么算法只需要一个？

What I'm having a hard time understanding- especially when looking at the entire pseudocode- is why it only takes one vertex as an argument? I need to find the cheapest airfare(shortest path) between two vertices. Why does the algorithm only require one?

推荐答案

Dijkstra会找到从提供顶点的最短路径（第一）到图表中的每个顶点。这就是为什么它只需要一个顶点作为输入。

Dijkstra's will find the shortest path from the provided vertex (first in your example) to every vertex in your graph. That's why it only takes one vertex as input.

这篇关于使用Dijkstra算法在邻接矩阵中找到最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！