Dijkstra算法求最短路径

Dijkstra算法求最短路径(C#版) 

行如下图的路径,(V0是中心):

经过该算法后转化为下图

using System;

using System.Collections;

using System.Text;

namespace Greedy

{   

    class Marx

    {

        private int[] distance;        

        private int row;

        private ArrayList ways = new ArrayList();

        public Marx(int n,params int[] d)

        {

            this.row = n;

            distance = new int[row * row];

            for (int i = 0; i < row * row; i++)

            {

                this.distance[i] = d[i];              

            }

            for (int i = 0; i < this.row; i++)  //有row个点，则从中心到各点的路有row-1条

            {

                ArrayList w = new ArrayList();

                int j = 0;

                w.Add(j);

                ways.Add(w);

            }

        }

        //------------------------------

        public void Find_way()

        {

            ArrayList S = new ArrayList(1);

            ArrayList Sr = new ArrayList(1);

            int []Indexof_distance=new int[this.row];

            for(int i=0; i < row; i++)

            { 

                Indexof_distance[i]=i;

            }

            S.Add( Indexof_distance[0] );        

            for (int i = 0; i < this.row; i++)

            {

                Sr.Add( Indexof_distance[i] );

            }

            Sr.RemoveAt(0);

            int[] D = new int[this.row];    //存放中心点到每个点的距离

         //---------------以上已经初始化了，S和Sr(里边放的都是点的编号)------------------

            int Count = this.row - 1;

            while (Count>0)

            {

                //假定中心点的编号是0的贪吃法求路径

                for (int i = 0; i < row; i++)

                    D[i] = this.distance[i];

                int min_num = (int)Sr[0];  //距中心点的最小距离点编号

                foreach (int s in Sr)

                {

                    if (D[s] < D[min_num]) min_num = s;

                }

                //以上可以排序优化

                S.Add(min_num);

                Sr.Remove(min_num);

                //-----------把最新包含进来的点也加到路径中-------------

                ((ArrayList)ways[min_num]).Add(min_num);

                //-----------------------------------------------

                foreach (int element in Sr)

                {

                    int position = element * (this.row) + min_num;

                    bool exchange = false;      //有交换标志

                    if (D[element] < D[min_num] + this.distance[position])

                        D[element] = D[element];

                    else

                    {

                        D[element] = this.distance[position] + D[min_num];

                        exchange = true;

                    }

                    //修改距离矩阵                   

                    this.distance[element] = D[element];

                    position = element * this.row;      

                    this.distance[position] = D[element];

                    //修改路径---------------

                    if (exchange == true)

                    {                       

                        ((ArrayList)ways[element]).Clear();

                        foreach (int point in (ArrayList)ways[min_num])

                            ((ArrayList)ways[element]).Add(point);

                    }

                }

                --Count;

           }

        }

        //----------------------------------------------------

        public void Display()

        {         

            //------中心到各点的最短路径----------

            Console.WriteLine("中心到各点的最短路径如下: \\n\\n");

            int sum_d_index = 0;

            foreach(ArrayList mother in ways)

            {

                foreach (int child in mother)

                    Console.Write("V{0} -- ", child+1);

                Console.WriteLine("    路径长 {0}",distance[sum_d_index++]);

            }

        }

    }

    class MainEnterPoint

    {   

        static void Main(string[] args)

        {

            int r;     //列数

            Console.Write("请输入点个数（含配送中心点）: ");

            Int32.TryParse(Console.ReadLine(), out r);

            Console.WriteLine("各点分别为: \\n");

            for (int i = 0; i < r; i++)

                Console.Write("V{0} ", i);

            Console.Write("  假定第一个点是配送中心");

            Console.WriteLine("\\n\\n输入各点之间的距离(无通径的用个大整数表示)\\n");

            int[] a = new int[r * r];            

            int da;

            for (int i = 0; i < r; i++)

            {

                for (int j = i + 1; j < r; j++)

                {

                    Console.Write("V{0} 到 V{1}的距离是:  ",i,j);

                    Int32.TryParse(Console.ReadLine(), out da);

                    a[i * r + j] = da;

                    Console.WriteLine();

                }

            }

            //----完善距离矩阵(距离矩阵其实可以是个上三角矩阵，

            //----但为了处理方便，还是将其完整成一个对称阵)-----------

            for (int i = 0; i < r; i++)

            {

                for (int j = 0; j < r; j++)

                {

                    if (i == j)

                    {

                        a[i * r + j] = 0;

                    }

                    a[j * r + i] = a[i * r + j];

                }

            }      

            Marx m=new Marx(r,a);

            Console.WriteLine();

            m.Find_way();

            m.Display();

        }

    }

}

//该程序不但能够算出从中心到各点的最短路径距离,而且把路径也保存了下来.

dijkstra最短路径问题 

# include

# include

# define maxlen 10

# define large 999

typedef struct

{

 int vexnum;

 char vexs[maxlen];

 int arcs[maxlen][maxlen];

}graph;

void init_graph(graph *g)

{

 int i=0,j=0;

 g->vexnum=5;

 for(i=0;i<5;i++)

  for(j=0;j<5;j++)

   g->arcs[i][j]=1000;

 g->arcs[0][1]=1;

 g->arcs[0][3]=3;

 g->arcs[0][4]=7;

 g->arcs[1][2]=2;

 g->arcs[2][3]=2;

 g->arcs[2][4]=2;

 g->arcs[3][4]=5;

 g->arcs[3][2]=3;

 g->arcs[3][1]=1;

 g->vexs[0]='a';

 g->vexs[1]='b';

 g->vexs[2]='c';

 g->vexs[3]='d';

 g->vexs[4]='e';

}

void shortpath_dijkstra(graph g)

{ 

 int cost[maxlen][maxlen];//cost[i][j]: The cost of i to j.

 int dist[maxlen];//dist[i]: The distance of source point to i.

 int path[maxlen];//The point passed by.

 int s[maxlen];//if s[i]=1,then i is in the source point gather.

 int i,j,n,v0,min,u;

 printf("Input the source point(1 means the first point):");

 scanf("%d",&v0);

 v0--;

 for(i=0;i {

  for(j=0;j  cost[i][j]=g.arcs[i][j];

 }

 for(i=0;i    { 

  dist[i]=cost[v0][i];

  if(dist[i]0) path[i]=v0;

   s[i]=0;

 }

 s[v0]=1;

 for(i=0;i    { 

  min=large;

  u=v0;

  for(j=0;j   if(s[j]==0&&dist[j]    {min=dist[j];u=j;}

  s[u]=1;   

  for(j=0;j   if(s[j]==0&&dist[u]+cost[u][j]   { 

    dist[j]=dist[u]+cost[u][j];

    path[j]=u;

            }

 }

 printf("Output\\n",v0);

 for(i=0;i  if(s[i]==1)

  { 

   u=i;

   while(u!=v0)

            { 

    printf("%c<-",g.vexs[u]);

    u=path[u];

            }

   printf("%c",g.vexs[u]);

   printf(":%d\\n",dist[i]);

        }

  else printf("%c<-%c:no path\\n",g.vexs[i],g.vexs[v0]);

}

int main()

{

 graph g;

 init_graph(&g);

 shortpath_dijkstra(g);

}

dijkstra最短路径问题 

用文件输入输出

input: n,k

     输入一个矩阵表示边的信息

output: n个数，表示k到各个点的最短路

program dijkstra;

const

 inp =  'input.txt';

 oup =  'output.txt';

 maxn=   100;

var

 ga   :    array[1..maxn,1..maxn] of integer;

 dist :    array[1..maxn]         of integer;

 s    :    array[1..maxn]         of    0..1;

 n,k  :    integer;

 fp   :    text;

procedure init;

var

 i,j: integer;

begin

 assign(fp,inp);  reset(fp);

 readln(fp,n,k);

 for i:=1 to n do

 for j:=1 to n do

 read(fp,ga[i,j]);

 close(fp);

end;

procedure main;

var

 i,j,w,m:integer;

begin

 fillchar(s,sizeof(s),0);

 for i:=1 to n do

 dist[i]:=maxint;

 dist[k]:=0;

 for i:=1 to n-1 do

 begin

      m:=maxint;

      for j:=1 to n do

       if (s[j]=0) and (dist[j]       begin

             m:=dist[j];

             w:=j;

       end;

       s[w]:=1;

       for j:=1 to n do

       if (s[j]=0) and (ga[w,j]>0) and (dist[w]+ga[w,j]        dist[j]:=dist[w]+ga[w,j];

 end;

end;

procedure print;

var

 i,j:integer;

begin

 assign(fp,oup);

 rewrite(fp);

 for i:=1 to n do

 write(fp,dist[i],' ');

 close(fp);

end;

begin

 init;

 main;

 print;

end.