Dijkstra算法求由顶点a到顶点h的最短路径_求下图顶点a到其余各个顶点的最短路径,要求给出求解过程

问题

下图使用Dijkstra算法求由顶点a到顶点h的最短路径，按实验报告模板编写算法。

解析

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

设计

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     
    dist[1]=0; 
    for(int i=0;i<n;i++)      
    {
        int t=-1;       
        for(int j=1;j<=n;j++)   
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;
        st[t]=true;   
        for(int j=1;j<=n;j++)           
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1; 
    return dist[n];
}

源码

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];  
int dist[N];   
bool st[N];    
int n,m;
int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     
    dist[1]=0;  
    for(int i=0;i<n;i++)      
    {
        int t=-1;      
        for(int j=1;j<=n;j++)   
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;
        st[t]=true;   
        for(int j=1;j<=n;j++)    
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1; 
    return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);    
                               
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);    
    }
    cout<<dijkstra()<<endl;
    return 0;
}