单源最短路径 dijkstra算法+邻接表优化

dijkstra:不能处理负权边，也不能判定负权回路的存在

求一点到其他所有点的最短路径

以点1到其他点的路径为例：

#include <iostream>
using namespace std;
int e[10][10];
int book[10];
int dis[10];
int inf=99999;
int main ()
{
    int n,m;
    scanf("%d%d",&n,&m);  //n是点的个数，m是有向边的个数
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j)e[i][j]=0;
            else e[i][j]=inf;
        }
    }
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[a][b]=c;
    }
    for(int i=1;i<=n;i++)dis[i]=e[1][i];
    for(int i=1; i<=n; i++)book[i]=0;
    book[1]=1;
   
    for(int i=1; i<=n-1; i++)//n-1次，每次找一个距离1点最近的点，以此扩展
    {
        int m=inf;
        int u=1;
        for(int j=1; j<=n; j++)
        {
            if(book[j]==0&&dis[j]<inf)  //找距离1最近的点，标记进p集合，用book表示
                                          //ps：p集合是已知最短路程的点，q集合是待定
            {
                if(dis[j]<m)
                {
                    m=dis[j];
                    u=j;
                }

            }
        }
        book[u]=1;
        for(int j=1;j<=n;j++)  //通过距离1最近的点的出边扩展
        {
            if(e[u][j]<inf)
            {
                if(dis[j]>dis[u]+e[u][j])
                {
                    dis[j]=dis[u]+e[u][j];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    return 0;
}

输入数据验证：

6 9 1 2 1 2 3 9 1 3 12 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4 输出：

0 1 8 4 13 17

邻接表优化：

#include <iostream>
using namespace std;
int book[100];
int dis[1000];
int main ()
{
    int n,m;
    cin>>n>>m;
    int u[m+1],v[m+1],w[m+1];
    int first[n+1],next[m+1];
    int i,j;
    for(i=1; i<=n; i++)first[i]=-1;
    for(i=1; i<=n; i++)
    {
        if(i==1)dis[i]=0;
        else dis[i]=99999;
    }
    book[1]=1;
    for(i=1; i<=m; i++)
    {
        cin>>u[i]>>v[i]>>w[i];
        if(u[i]==1)dis[v[i]]=w[i];
        next[i]=first[u[i]];//  以下两行是邻接表的重要代码，是用数组实现链表
        first[u[i]]=i;      //  first[i]存储第i点的第一条出边的编号
    }                       //  next[i]存储第i边的下一边的编号
                            //可以将first理解为链表的头指针,next中含有其他节点
    int k;
    for(i=1; i<=n-1; i++)
    {
        k=first[1];
        int s=99999;
        int z;
        for(j=1; j<=n; j++)
        {
              if(book[j]==0&&dis[j]<s)
              {
                  z=j;
                  s=dis[j];
              }
        }
        book[z]=1;
        k=first[z];    //这里用邻接表优化 不在O(n)遍历  
        while(k!=-1)
        {
            if(dis[v[k]]>dis[z]+w[k])
            {
                dis[v[k]]=dis[z]+w[k];
            }
            k=next[k];
        }
    }
    for(j=1; j<=n; j++)
    {
        if(j>1)cout<<" ";
        cout<<dis[j];
    }
    return 0;
}
/*  可用一下数据验证  输入：
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
*/
/*输出
0 1 8 4 13 17
*/