最短路径Dijkstra

给定图G(v,e)，
求一条从起点到终点的路径,
使得这条路径上经过的所有边的边权之和最小

对任意给出的图G(v,e)和起点S，终点T，
如何求从S到T的最短路径
从V1->V4,最短距离是2,对应的路径为{V1->V3->V4}

解决最短路径问题的常用算法：
Dijkstra，用于解决单源最短路问题
即给定图G和起点s，通过算法得到s到达其他每个顶点的最颠路径

对图G(V,E)设置集合S，存放已经被访问的顶点，
然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记作u)，
访问并加入加入集合S，
之后，
令顶点u为中介点，
优化起点s与所有从u能到达的顶点v值件的最短距离。
这样操作执行n次(n为顶点个数)，
知道集合S包含所有的顶点

1.未被攻占的城市
2.最短距离最小的城市
3.攻占该城市，开放从该城市出发的边，更新最短距离

例子1
有向边
输出从起点到各个顶点的最短路径

//G为图，一般为全局变量
//数组d为起点s到达各个顶点的最短路径长度。

Dijkstra(G,d[],s){
	初始化;
	for(循环n次){
		u=使d[u]最小的还未被访问的顶点的标号;
		记录u已经被访问;
		for(从u出发能到达的所有顶点v){//n
			if(v未被访问&&以u为中介使得s到达顶点v的最短距离d[v]更优)
				优化d[v];
		}
	}
}

void Dijkstra(int s){
	fill(d,d+N,INF);
	d[s]=0;
	for(int i=0;i<n;i++){
		int u=-1,MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				MIN=d[j];
				u=j;
			}
		}
		if(u==-1)return;
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
				d[v]=d[u]+G[u][v];	
				pre[v]=u;	
			}
		}	
 	}
}

// 6 8 0//顶点数 边数 顶点编号
// 0 1 1
// 0 3 4
// 0 4 4
// 1 3 2
// 2 5 1
// 3 2 2
// 3 4 3
// 4 5 3
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1000;
const int INF=1000000000;
int n,m,s;
int G[N][N];
int d[N];//记录从起点到达各个顶点的最短路径的长度
bool vis[N]={false};
int pre[N];//新添加的顶点


void Dijkstra(int s){
    fill(d,d+N,INF);
    d[s]=0;//起点到起点的距离长度是0
    for(int i=0;i<n;i++){//0//1
        int MIN=INF,u=-1;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){//d[0]==0<INF//d[1]==1<INF//1.未攻占，最短路径最小的城市
               u=j;//(u,v)//u=0//u=1
               MIN=d[j];//MIN=0//MIN=1
            }
        }
        if(u==-1)return;
        vis[u]=true;//vis[0]=true//vis[1]=true
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){//2.开放，更新最短路径
                //vis[v]==false&&G[0][v]!=INF
                // 0 1 1--G[0][1]==1!=INF--d[0]+G[0][1]==1<d[1]==INF
                // 0 3 4--G[0][3]==4!=INF--d[0]+G[0][3]==4<d[3]==INF
                // 0 4 4--G[0][4]==4!=INF--d[0]+G[0][4]==4<d[4]==INF
                
                //vis[v]==false&&G[1][v]!=INF
                // 1 3 2--G[1][3]=2!=INF---d[1]+G[1][3]==3<d[3]==4
                d[v]=d[u]+G[u][v];
                //d[1]=1
                //d[3]=4
                //d[4]=4
                
                //d[3]=3
                pre[v]=u;
                //pre[1]=0
                //pre[3]=0
                //pre[4]=0
                
                //pre[3]=1
            }
        }
    }
    
}


int main()
{
    cin>>n>>m>>s;
    fill(G[0],G[0]+N*N,INF);
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        //有向图--单向
        G[u][v]=w;
    }
    Dijkstra(s);//传入起点
    for (int i = 0; i < n; i++)
		cout << d[i] << " ";
    return 0;
}
// 6 8 0
// 0 1 1
// 0 3 4
// 0 4 4
// 1 3 2
// 2 5 1
// 3 2 2
// 3 4 3
// 4 5 3
// 0 1 5 3 4 6

//输入数据
//6 8 0//顶点数 边数 起点编号
//0 1 1//边0->1的边权为1
//0 3 4 
//0 4 4
//1 3 2
//2 5 1
//3 2 2
//3 4 3 
//4 5 3
//输出结果
//最短路径
//0 1 5 3 4 6

//邻接矩阵
//有向图
#include <iostream>
using namespace std;
const int N = 1000;
const int INF = 1000000000;
int n, m, s, G[N][N];//顶点数,边数,起点


int d[N];//起点到达各个点的最短路径长度
bool vis[N] = { false };//初始化 未访问
int pre[N];//从起点到顶点v的最短距离上v的前一个顶点(新添加)


void Dijkstra(int s) {//s为起点
	fill(d, d + N, INF);//fill将整个d数组赋值为INF
	d[s] = 0;//起点s到自身的距离是0
	for (int i = 0; i < n; i++) {//循环n次
		int u = -1, MIN = INF;//MIN存放该最小的d[u]
		for (int j = 0; j < n; j++) {
			if (vis[j] == false && d[j] < MIN) {//
				u = j;
				MIN = d[j];
			}
		}
		if (u == -1)return;//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
		vis[u] = true;
		for (int v = 0; v < n; v++) {
			if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
				d[v] = d[u] + G[u][v];
				pre[v] = u;
			}
		}
	}

}


int main() {

	cin >> n >> m >> s;//6 8 0
	fill(G[0], G[0] + N * N, INF);//初始化图G------边权的设置--无限大//fill???????????
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;//a->b以及a->b的边权
		G[u][v] = w;//有向边
	}
	Dijkstra(s);//Dijkstra算法入口//起点
	for (int i = 0; i < n; i++)
		cout << d[i] << " ";
		return 0;
}

/*

6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3

*/

/*
6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
0 1 5 3 4 6


*/