qt用dijkstra算法计算最短路径加以注释
时间: 2023-11-15 13:52:30 浏览: 45
//首先定义一个邻接矩阵来存储图的信息
int graph[MAX][MAX];
//定义一个数组来记录起点到各个顶点的距离
int distance[MAX];
//定义一个数组来记录是否已经访问过该顶点
bool visited[MAX];
//定义一个函数来计算起点到终点的最短路径
void dijkstra(int start, int end)
{
//初始化距离和访问数组
for(int i = 0; i < MAX; i++)
{
distance[i] = INF;
visited[i] = false;
}
//起点到自己的距离为0
distance[start] = 0;
//循环遍历每个顶点
for(int i = 0; i < MAX; i++)
{
//找到距离起点最近的顶点
int minDist = INF;
int minIndex = 0;
for(int j = 0; j < MAX; j++)
{
if(!visited[j] && distance[j] < minDist)
{
minDist = distance[j];
minIndex = j;
}
}
//标记已访问
visited[minIndex] = true;
//更新起点到其他顶点的距离
for(int j = 0; j < MAX; j++)
{
if(!visited[j] && graph[minIndex][j] != INF && distance[minIndex] + graph[minIndex][j] < distance[j])
{
distance[j] = distance[minIndex] + graph[minIndex][j];
}
}
}
//输出最短路径
cout << "The shortest distance from " << start << " to " << end << " is " << distance[end] << endl;
}