qt用dijkstra邻接链表算最短路径
时间: 2023-09-19 13:05:04 浏览: 43
下面是Qt中使用Dijkstra算法求解最短路径的示例代码,使用邻接链表存储图:
```
//定义邻接链表节点
struct Node{
int v; //邻接节点
int w; //边权重
Node(int v, int w):v(v),w(w){}
};
//定义邻接链表
typedef vector<Node> AdjList;
vector<AdjList> graph;
//Dijkstra算法求解最短路径
vector<int> dijkstra(int start, int n){
vector<int> dist(n, INT_MAX);
vector<bool> visited(n, false);
dist[start] = 0;
for(int i=0; i<n; i++){
int u = -1;
for(int j=0; j<n; j++){
if(!visited[j] && (u==-1 || dist[j]<dist[u]))
u = j;
}
visited[u] = true;
for(auto& node:graph[u]){
int v = node.v;
int w = node.w;
if(dist[u]!=INT_MAX && dist[v]>dist[u]+w){
dist[v] = dist[u] + w;
}
}
}
return dist;
}
```
使用示例:
```
//初始化邻接链表
graph.resize(n);
for(int i=0; i<m; i++){
int u, v, w;
cin>>u>>v>>w;
graph[u].push_back(Node(v,w));
}
//求解最短路径
vector<int> dist = dijkstra(start, n);
//输出结果
for(int i=0; i<n; i++){
cout<<dist[i]<<" ";
}
cout<<endl;
```