贪心算法实现最短路径问题迪杰斯特拉C++

贪心算法是一种常见的求解最短路径问题的方法，其中迪杰斯特拉算法是其中的一种实现方式。下面是迪杰斯特拉算法的具体步骤：

1. 创建一个大小为n的数组dist，用来记录源点到每个顶点的最短距离。初始化为无穷大，除了源点为0。

2. 创建一个大小为n的数组visited，记录每个顶点是否已经被访问过，初始值为false。

3. 在dist数组中找到未被访问过的距离最小的顶点v，并将visited[v]设置为true。

4. 对于顶点v的每个邻接点u，如果visited[u]为false，并且源点到u的距离比源点到v加上v到u的距离小，则更新dist[u]为这个更小的值。

5. 重复步骤3和步骤4，直到所有顶点都被访问过。

下面是迪杰斯特拉算法的C++代码实现：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int n,m,s,t;
int g[N][N],dist[N];
bool visited[N];

void Dijkstra(int s){
    memset(visited,false,sizeof(visited));
    memset(dist,INF,sizeof(dist));
    dist[s] = 0;

    for(int i=0;i<n;i++){
        int v = -1;
        for(int j=0;j<n;j++){
            if(!visited[j] && (v==-1 || dist[j]<dist[v])) v = j;
        }
        visited[v] = true;
        for(int u=0;u<n;u++){
            if(!visited[u] && g[v][u]!=INF && dist[v]+g[v][u]<dist[u]){
                dist[u] = dist[v]+g[v][u];
            }
        }
    }
}

int main(){
    cin>>n>>m>>s>>t;
    memset(g,INF,sizeof(g));
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = c;
    }
    Dijkstra(s);
    cout<<dist[t]<<endl;
    return 0;
}