单源最短路径——贪心算法

Dijsktra：

#include<iostream>
using namespace std;

const int INF = 0x3f3f3f3f;  //表示无穷大
const int N = 5;  //5个结点

//构造图矩阵,c[i][j]表示边(i,j)的权
int c[N + 1][N + 1] = {
	{0, 0, 0, 0, 0, 0},
	{0, INF, 10, INF, 30, 100},
	{0, INF, INF, 50, INF, INF},
	{0, INF, INF, INF, INF, 10},
	{0, INF, INF, 20, INF,  60},
	{0, INF, INF, INF, INF, INF}
};

void Dijsktra(int n, int v, int dist[], int prev[]){
	bool s[N]; //判断是否访问过
	for(int i = 2;	i <= N; i++){
		dist[i] = c[v][i];
		s[i] = false;
		if(dist[i] == INF)
			prev[i] = 0;
		else
			prev[i] = v;
	}
	s[v] = true; dist[v] = 0;

	for(int i = 1; i < N; i++){
		int u = v;
		int temp = INF;
		for(int j =1; j <= N; j++){
		//找最小的
			if(!s[j] && dist[j] <temp){
				u = j;
				temp = dist[j];
			}
		}
		s[u] = true;

		for(int j = 1; j <= N; j++){
			if(!s[j] && c[u][j] < INF){
				int newdist = dist[u] + c[u][j];
				if(newdist < dist[j]){
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}
}
				
void traceback(int i, int prev[]){
	if(prev[i] != 1) 
		traceback(prev[i], prev);
	cout << prev[i] << "->";
	return ;
}
int main(){

	int prev[N]; // perv[3]=2第3个结点是由2结点通过来的
	int dist[N];  //从源到顶点i的最短路径长度
	int v = 1; //设置源顶顶点为1
	cout << "图构成的矩阵是：" << endl;
  	for (int i = 1; i <= N; i++) {
   		for (int j = 1; j <= N; j++) {
			if (c[i][j] != INF)
				cout << c[i][j] << "\t";
      		else
		        cout << "∞\t";
    	}
   		cout << endl;
  	}

	Dijsktra(N, v, dist, prev);
	for (int i = 2; i <= N; i++) {
    	cout << "源点1到点" << i << "的最短路径长度为:" << dist[i] << endl;
    	traceback(i, prev);
    	cout << i << endl;
	}
	
	return 0;
}