一、预备知识：
用优先队列做大小根堆
注意：是非负权值的单源最短路径的STL实现，权值是负的不能用dijkstra算法
解释在第一段
二、代码：
#include<iostream>#include<cstdio>#include<list>#include<queue>#include<set>#define INF 9999999using namespace std;class Graph{int n;list<pair<int,double> > *adj;//邻接表 public:Graph(int _n){n = _n;adj = new list<pair<int, double> >[_n];}void addEdge(int u, int v, double weight){adj[u].push_back(make_pair(v,weight)); }void shortestPath(int src); };
void Graph::shortestPath(int src){//用优先队列当小根堆，pair排序时先按first升序排，相等再按second升序排//因要按weight来排序，所以把weight放前面priority_queue< pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > pq; vector<double>dist(n,INF);vector<int>parent(n,-1);//parent[v] = u，由u到vvector<double>weights(n,INF);//weights[v]记录从src到v分支上某点到v的最小权值 pq.push(make_pair(0,src));dist[src] = 0;parent[src] = 0;weights[src] = 0;while(!pq.empty()){int u = pq.top().second;pq.pop();list<pair<int,double> >::iterator it;for(it = adj[u].begin(); it != adj[u].end(); it++){int v = it->first; //获取顶点 double weight = it->second; //获取weight if(dist[v] > dist[u]+weight) {dist[v] = dist[u] + weight;pq.push(make_pair(dist[v],v));parent[v] = u;//记录从哪到v最短 weights[v] = weight;//记录到v的那条路径的路径 }}} for(int i = 0 ;i < n; i++){cout<<parent[i]<<"->"<<i<<" dist["<<i<<"]: "<<dist[i]<<" \t the weight "<<"from "<<parent[i]<<" to "<<i<<" is "<<weights[i]<<endl; }}
int main() {int V = 9; Graph g(V); g.addEdge(0, 1, 4); g.addEdge(0, 7, 8); g.addEdge(1, 2, 8); g.addEdge(1, 7, 11); g.addEdge(2, 3, 7); g.addEdge(2, 8, 2); g.addEdge(2, 5, 4); g.addEdge(3, 4, 9); g.addEdge(3, 5, 14); g.addEdge(4, 5, 10); g.addEdge(5, 6, 2); g.addEdge(6, 7, 1); g.addEdge(6, 8, 6); g.addEdge(7, 8, 7); g.shortestPath(0); return 0; }
