图 最短路 Dijkstra 迪杰斯特拉算法

这个算法适合于解决单源最短路径问题，即规定了一个起点，然后求这个起点到各个点的最短路，感觉和动态规划有点像，而且他这个数组设置的也很有特色，和动态规划也有异曲同工之妙。

设置d[i] 表示从起点到i这个位置所花费的最小路程。

#include 
using namespace std;
#define MAXN 0x3fffffff 
int mp[500][500];
int main()
{
	int N,M;
	cin >> N >> M;//表示n个范围 M个数据 E为终结点 0为起始点 
	for (int i = 0;i> a >> b >> c;
		mp[a][b] = c;//从a到b需要花费c代价 
	} 
	 int d[500];//表示从0开始到此点的最小距离 
	 int vis[500];
	 for (int i = 0;i 
而下面的更新数据就显得更有意思了，如果mp【u】【v】存在，说明u到v是存在相通的，而加上
 
d【u】相当于是起点到u的最小距离 ，最后再给出一个判断 ，就可以把起点到v的最小距离求出来了，但是这个最小不一定是最终的，只是目前基础上比较优秀的，当他被标记为已经访问过，才能保证他就是最优的了。
 
 
 这份伪代码的话，可以很好的描述上面的思路。
 
 
 
很简单的一个题，用上面的思路就可以写出来。
 
#include 
using namespace std;
#define MAXN 0x3ffff
int mp[20005][20005];
int d[20005];
int n,m;
bool vis[20005];
void Dij(int s)
{ 
    for (int i = 0;i<=n;i++) d[i]=MAXN;
    d[s] = 0;
    for (int i = 1;i<=n;i++)
    {
        int u = 0,min = MAXN;
        for (int j = 1;j<=n;j++)//只是寻找最小值
        {
            if (!vis[j] && d[j]> n >> m;
    for (int i = 0;i<=n;i++)
        for (int j = 0;j<=n;j++)
            mp[i][j] = MAXN;
    while (m--)
    {
        int u,v,l;
        scanf ("%d%d%d",&u,&v,&l);
        mp[u][v] = l;
    }
    Dij(1);
    for (int i = 2;i<=n;i++)
    {
        cout << d[i] << endl;
    }
    return 0;
}
 
很显然，写的是对的，但是占用内存太多了，爆栈了，所以还得修改，二维数组不能开的这么随意。内存最多开到1e8，也就是10000*10000，所以二维数组方法行不通了。
 
#include
int main()
{
	int n,m,t,i,k,check,dis[20005],u[200005],v[200005],w[200005];
	int inf=99999999;
	scanf("%d %d",&n,&m);
	for(i=0;idis[u[i]]+w[i]&&dis[u[i]] 
这个方法就非常的妙，牛逼多了呀。
 
特别是那个关键代码处，存储的是起点，终点，权值，而根据d【i】数组的含义可以得出
 
d【终点】= d【起点】+权值 。然后遍历更新，很妙哇。非常好，简洁而且省空间。因为每个路径都试一遍，所以会存在最小值的，O（n*n） -> O(n*m) 时间方面也很优秀，真的不错。
 
#include 
using namespace std;
#define MAXN 0x3ffffff
int A[200005],B[200005],C[200005];
int d[200005];
int n,m;
void Dij(int s)
{ 
    for (int i = 1;i<=n;i++) d[i]=MAXN;
    d[s] = 0;
    for (int i = 1;i<=n;i++)
    {
        int f = 0;
        for (int j = 0;jd[A[j]]+C[j])
            {
                f = 1;
                d[B[j]] = d[A[j]] + C[j];
            }
        }
        if (f==0) break;
    }
}
int main()
{
   cin >> n >> m;
    for (int i = 0;i 
 自己ac的代码，有几个很需要注意的点，首先就是数组的大小问题，必须以m为标准，所以要开到2e6 而n范围只有2E5。
 
实际上还有几个地方不太理解的，就是循环里面的判断句，为什么不是小于号，按常识，不应该求最短，只有小于才可以换值吗，为什么恰恰相反，取大于还是对的。得好好思考一番。
 
哎，脑子一下短路了，是没错的，就是如果后面的值比前面的要小的话，就赋值给前面。