单源最短路径问题c++实现（贪心算法）

• • 1.认真审阅题目，明确题目的已知条件和求解的目标；
  • 2.问题建模；
  • 3.算法设计；
  • 4.编码实现；
  • 5.测试数据；
  • 6.程序运行结果；

给定一个有向带权图 G = （V，E），其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。
计算从源点到所有其他点的最短路径长度，这里的路径长度指的是路径上经过的所有边上的权值之和。这个问题通常称为单源最短路径的问题。

Dijkstra算法思想：
按各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径的方法，即先求出长度最短的一条路径，再参照它求出长度次短的一条路径，以此类推，直到源点到其他各个顶点的最短路径全部求出为止。
算法设计：
假定源点u，顶点集合V被划分为两部分，集合S和V-S，其中S中的顶点到源点的最短路径的长度已经确定，集合V-S中所包含的顶点到源点的最短路径的长度待定，称从源点出发，只进过S中的点到达V-S中的点的路径为特殊路径，

#include 
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;
}

-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

源点1到源点5的最短路径长度为：60
路径为：
1->4->3->5 

第二组：

源点1到源点5的最短路径长度为：20
路径为：
1->3->5