问题描述：
给定一个带权有向图G = (V, E), 其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算源到所有其他各定点的最短长度。这里路的长度是指路上各边权之和。这个问题通常成为单源最短路径问题。
解法：
用优先队列式分支限界法，代码核心跟贪心的Dijkstra算法差不多相同，要首先学会使用优先队列的使用。
贪心的Dijkstra算法实现见Dijkstra算法实现
代码：
#include <bits/stdc++.h>using namespace std;class MinHeapNode{public:int id;int length; //从起始点 v 到点 id 的距离public:friend bool operator < (const MinHeapNode &a, const MinHeapNode &b){return a.length < b.length;}friend bool operator > (const MinHeapNode &a, const MinHeapNode &b){return a.length > b.length;}};const int max_ = 0x3f3f3f;int Graph[100][100];int dist[100];int pre[100];int n, m, v;void OutPutPath(int i){if(i == pre[i]){printf("%d", i);return;}else{OutPutPath(pre[i]);printf(" %d", i);}}void OutPut(){for(int i = 1; i <= n; ++i){if(i != v){printf("点 %d 到 %d 的最短距离是 %d\n", v, i, dist[i]);printf("路径为：");OutPutPath(i);printf("\n");}}}void ShortestPaths(){priority_queue<MinHeapNode, vector<MinHeapNode>, greater<MinHeapNode> > q; // 小顶堆memset(dist, max_, sizeof(dist));dist[v] = 0; //不要忘了这里的初始化pre[v] = v;MinHeapNode cur_p;cur_p.id = v;cur_p.length = 0;q.push(cur_p);while(true){if(q.empty() == 1)break;cur_p = q.top(); //取出堆顶的点q.pop(); // 在优先队列中删除刚取出的点// cout << q.size() << endl;for(int i = 1; i <= n; ++i){if(Graph[cur_p.id][i] != max_ && (cur_p.length + Graph[cur_p.id][i] < dist[i])){dist[i] = cur_p.length + Graph[cur_p.id][i];pre[i] = cur_p.id;MinHeapNode temp;temp.id = i;temp.length = dist[i];q.push(temp);}}}}void InPut(){int x, y, len;scanf("%d %d %d", &v, &n, &m);memset(Graph, max_, sizeof(Graph));for(int i = 1; i <= m; ++i){scanf("%d %d %d", &x, &y, &len);Graph[x][y] = Graph[y][x] = len;//printf("%d\n", i);}}int main(){InPut();ShortestPaths();OutPut();}
测试样例：
输入：
1 5 7
1 2 10
1 5 100
1 4 30
2 3 50
3 5 10
4 3 20
4 5 60
输出：
点 1 到 2 的最短距离是 10
路径为：1 2
点 1 到 3 的最短距离是 50
路径为：1 4 3
点 1 到 4 的最短距离是 30
路径为：1 4
点 1 到 5 的最短距离是 60
路径为：1 4 3 5
运行截图：
