dijkstra.cpp

迪杰斯特拉最短路径算法（未优化

//无向图，输入0表示无路径，采用邻接矩阵存储
#include<iostream>
#define max 99999
using namespace std;


int n;

//pre[i]:表示  i  的前一个节点是什么
//dist[i]:表示  已标记的集合  到  i  的 现阶段所能达到的最小值 
//vis[i]:表示访问与否 

int Dijkstra(int **a, int *pre, int source)
{
   int *dist=new int[n+1];
   bool *vis=new bool[n+1];
   int i;
   int min=max, pos=-1;
   vis[source]=true;
   pre[source]=-1;
   for (i=1; i!=n+1; ++i)
   {
       if (i == source)
          continue;
       dist[i]=a[source][i];
       vis[i]=false;
       if (dist[i] == 0) //说明无路径 
          pre[i]=0;
       else
          pre[i]=source;
       if (dist[i]!=0 && dist[i]<min)
       {
           pos=i;
           min=dist[i];
       }
   }
   if (pos == -1)   //源点到其他点均无路径 
      return -1;
   bool flag=true;
   int counts=n-1;
   while (flag && --counts)
   {
       vis[pos]=true;
       flag=false;
       for (i=1; i!=n+1; ++i)
       {
           if (vis[i] == true)
              continue;
           if ( (dist[i]==0 && a[pos][i]!=0) || (a[pos][i]!=0 && dist[i]>dist[pos]+a[pos][i]) )   //Dijkstra 
           {
              dist[i]=dist[pos]+a[pos][i];   //更新dist数组 
              pre[i]=pos;   //修改当前节点的前节点 
           }
       }
       min=max;
       for (i=1; i<=n; ++i)
       {
           if (vis[i] == true)
              continue;
           if (dist[i]!=0 && dist[i]<min)
           {
              pos=i;
              min=dist[i];
              flag=true;
           }
       }
   }
   delete []dist;
   delete []vis;
   return 0;
}


int main()
{
    int i, j;
    cin>>n;
    int **a=new int*[n+1];
    for (i=0; i!=n+1; ++i)
       a[i] = new int[n+1];

    int *pre=new int[n+1];

    for (i=1; i<=n; ++i)
       for (j=1; j<=n; ++j)
           cin>>a[i][j];

    int source;
    cin>>source;
    int bl=Dijkstra(a, pre, source);
    if (bl==0) //执行成功，找到路径 
       for (int i=1; i!=n+1; ++i)
           printf("%d ", pre[i]);
    delete []a;
    delete []pre;
    system("pause");
    return 0;
}