1.认真审阅题目，明确题目的已知条件和求解的目标；
给定一个有向带权图 G = （V，E），其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。
计算从源点到所有其他点的最短路径长度，这里的路径长度指的是路径上经过的所有边上的权值之和。这个问题通常称为单源最短路径的问题。
2.问题建模；
3.算法设计；
Dijkstra算法思想：
按各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径的方法，即先求出长度最短的一条路径，再参照它求出长度次短的一条路径，以此类推，直到源点到其他各个顶点的最短路径全部求出为止。
算法设计：
假定源点u，顶点集合V被划分为两部分，集合S和V-S，其中S中的顶点到源点的最短路径的长度已经确定，集合V-S中所包含的顶点到源点的最短路径的长度待定，称从源点出发，只进过S中的点到达V-S中的点的路径为特殊路径，
4.编码实现；
#include <bits/stdc++.h>
using namespace std;
#define N 5
#define M 9999999
void Dijkstra(int n, int v, int dist[], int p[], int c[][N+1])
{
bool s[N+1];//顶点集合S
for(int i = 1; i <= n; i++){
dist[i] = c[v][i];//从源点到顶点i的最短特殊路径长度
s[i] = false;
if(dist[i] == M){
p[i] = 0; // 从源点到顶点i的最短路径上千一个顶点
}
else
{
p[i] = v;
}
}
dist[v] = 0;
s[v] = true;
for(int i = 1; i < n; i++){
int temp = M;
int u = v;//上一顶点
//找到具有最短特殊路径长度的顶点u
for(int j = 1; j <= n; j++){
if((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = true;
//更新dist值
for(int j = 1; j <= n; j++){
if((!s[j]) && c[u][j] < M)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j]){
dist[j] = newdist;
p[j] = u;
}
}
}
}
}
//输出最短路径v源点，i终点
void Traceback(int v, int i, int p[])
{
//源点等于终点，即找出全部路径
if(v == i){
cout << i;
return;
}
Traceback(v, p[i], p);
cout << "->" << i;
}
int main(){
int v = 1;//源点 为1
int dist[N+1];//从源点到顶点i的最短特殊路径长度
int p[N+1]; //从源点到顶点i的最短路径上其哪一个顶点
//带权有向图的邻接矩阵，行和列从下标从1开始
int c[N+1][N+1];
//输入：如果输入-1，代表两个点不是邻接点，初始化为M(代表无穷大)
cout << "带权有向图的邻接矩阵为：" << endl;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
cin >> c[i][j];
if(c[i][j] == -1){
c[i][j] = M;
}
}
}
//寻找最短路径
Dijkstra(N, v, dist, p, c);
//输出
cout << "源点1到源点5的最短路径长度为：" << dist[5] << endl;
cout << "路径为：" << endl;
Traceback(1, 5, p);
return 0;
}
5.测试数据；
-1 10 -1 30 100
-1 -1 50 -1 -1
-1 -1 -1 -1 10
-1 -1 20 -1 60
-1 -1 -1 -1 -1
第二组：
-1 30 10 30 60
-1 -1 10 80 -1
-1 -1 -1 -1 10
-1 -1 40 -1 70
-1 -1 -1 -1 -1
6.程序运行结果；
源点1到源点5的最短路径长度为：60
路径为：
1->4->3->5
第二组：
源点1到源点5的最短路径长度为：20
路径为：
1->3->5
