首页 > 其他 > 详细

最短路问题

时间:2019-07-26 17:12:20      阅读:71      评论:0      收藏:0      [点我收藏+]

Floyd算法是多源最短路算法,复杂度最高(n^3),通常用在点比较少的起点不固定的问题中。能解决负边(负权)但不能解决负环。  (暴力)
Dijkstra算法是单源最短路算法,最常用时间复杂度(n^2)优化后可以达到(nlogn),不能解决负边问题,稀疏图(点的范围很大但是边不多,边的条数|E|远小于|V|²)需要耗费比较多的空间。
SPFA算法适合稀疏图,可以解决带有负权边,负环的问题,但是在稠密图中效率比Dijkstra要低。 (稠密图 就是点多边少)

http://acm.hdu.edu.cn/showproblem.php?pid=2544

题目大意:输入a点输入b点输入权值c

求最短路

dijkstra做法

#include <iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 101
int g[maxn][maxn];
int dist[maxn];
int sure[maxn];
int n,m;
void dijkstra(int begin)
{
    memset(dist,0x3f3f3f,sizeof(dist));
    memset(sure,0,sizeof(sure));
    dist[begin]=0;
    while(1)
    {
        int i,u=-1,v;
        int min=0x3f3f3f;
        for(i=1;i<=n;i++)
        {
            if(!sure[i]&&dist[i]<min)    //检查是否还有更短路线
            {
                min=dist[i];
                u=i;
            }
        }
        if(u==-1)
            break;
        sure[u]=1;
        for(v=1;v<=n;v++)
        {
            if(g[u][v]!=-1&&dist[v]>dist[u]+g[u][v])      //更新最短路线
            {
                dist[v] = dist[u] + g[u][v] > dist[v] ? dist[v]: dist[u]+g[u][v];
                //最小值
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)&&(m&&n))
    {
        int a,b,c;
        memset(g,-1,sizeof(g));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a][b] = c;
            g[b][a] = c;
        }
        dijkstra(1);
        printf("%d\n",dist[n]);
    }
    return 0;
}

 

最短路问题

原文:https://www.cnblogs.com/AAAzhuo/p/11251404.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!