欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C#实现的最短路径分析

程序员文章站 2023-12-05 20:53:04
复制代码 代码如下:using system; using system.collections.generic; using system.linq;...
复制代码 代码如下:

using system;
 using system.collections.generic;
 using system.linq;
 using system.text;

 namespace consoleapplication1
 {
     class program
     {
         static int length = 6;
         static string[] shortedpath = new string[length];
         static int nopath = 2000;
         static int maxsize = 1000;
         static int[,] g =
         {
             { nopath, nopath, 10, nopath, 30, 100 },
             { nopath, nopath, 5, nopath, nopath, nopath },
             { nopath, nopath, nopath, 50, nopath, nopath },
             { nopath, nopath, nopath, nopath, nopath, 10 },
             { nopath, nopath, nopath, 20, nopath, 60 },
             { nopath, nopath, nopath, nopath, nopath, nopath }
         };
         static string[] pathresult = new string[length];

         static int[] path1 = new int[length];
         static int[,] path2 = new int[length, length];
         static int[] distance2 = new int[length];

         static void main(string[] args)
         {
             int dist1 = getshortedpath(g, 0, 1, path1);
             console.writeline("点0到点5路径:");
             for (int i = 0; i < path1.length; i++)
                 console.write(path1[i].tostring() + " "); 
             console.writeline("长度:" + dist1);

 
             console.writeline("\r\n-----------------------------------------\r\n");

             int[] pathdist = getshortedpath(g, 0, path2);
             console.writeline("点0到任意点的路径:");
             for (int j = 0; j < pathdist.length; j++)
             {
                 console.writeline("点0到" + j + "的路径:");
                 for (int i = 0; i < length; i++)
                     console.write(path2[j, i].tostring() + " ");
                 console.writeline("长度:" + pathdist[j]);
             }
             console.readkey();

         }

 
         //从某一源点出发,找到到某一结点的最短路径
         static int getshortedpath(int[,]g, int start, int end,int [] path)
         {
             bool[] s = new bool[length]; //表示找到起始结点与当前结点间的最短路径
             int min;  //最小距离临时变量
             int curnode=0; //临时结点,记录当前正计算结点
             int[] dist = new int[length];
             int[] prev = new int[length];

             //初始结点信息
             for (int v = 0; v < length; v++)
             {
                 s[v] = false;
                 dist[v] = g[start, v];
                 if (dist[v] > maxsize)
                     prev[v] = 0;
                 else
                     prev[v] = start;
             }
             path[0] = end;
             dist[start] = 0;
             s[start] = true;
             //主循环
             for (int i = 1; i < length; i++)
             {
                 min = maxsize;
                 for (int w = 0; w < length; w++)
                 {
                     if (!s[w] && dist[w] < min)
                     {
                         curnode = w;
                         min = dist[w];
                     }
                 }

                 s[curnode] = true;
                 for (int j = 0; j < length; j++)
                     if (!s[j] && min + g[curnode, j] < dist[j])
                     {
                         dist[j] = min + g[curnode, j];
                         prev[j] = curnode;
                     }

             }
             //输出路径结点
             int e = end, step = 0;
             while (e != start)
             {
                 step++;
                 path[step] = prev[e];
                 e = prev[e];
             }
             for (int i = step; i > step/2; i--)
             {
                 int temp = path[step - i];
                 path[step - i] = path[i];
                 path[i] = temp;
             }
             return dist[end];
         }

 

 

 
         //从某一源点出发,找到到所有结点的最短路径
         static int[] getshortedpath(int[,] g, int start, int[,] path)
         {
             int[] pathid = new int[length];//路径(用编号表示)
             bool[] s = new bool[length]; //表示找到起始结点与当前结点间的最短路径
             int min;  //最小距离临时变量
             int curnode = 0; //临时结点,记录当前正计算结点
             int[] dist = new int[length];
             int[] prev = new int[length];
             //初始结点信息
             for (int v = 0; v < length; v++)
             {
                 s[v] = false;
                 dist[v] = g[start, v];
                 if (dist[v] > maxsize)
                     prev[v] = 0;
                 else
                     prev[v] = start;
                 path[v,0] = v;
             }

             dist[start] = 0;
             s[start] = true;
             //主循环
             for (int i = 1; i < length; i++)
             {
                 min = maxsize;
                 for (int w = 0; w < length; w++)
                 {
                     if (!s[w] && dist[w] < min)
                     {
                         curnode = w;
                         min = dist[w];
                     }
                 }

                 s[curnode] = true;

                 for (int j = 0; j < length; j++)
                     if (!s[j] && min + g[curnode, j] < dist[j])
                     {
                         dist[j] = min + g[curnode, j];
                         prev[j] = curnode;
                     }

 
             }
             //输出路径结点
             for (int k = 0; k < length; k++)
             {
                 int e = k, step = 0;
                 while (e != start)
                 {
                     step++;
                     path[k, step] = prev[e];
                     e = prev[e];
                 }
                 for (int i = step; i > step / 2; i--)
                 {
                     int temp = path[k, step - i];
                     path[k, step - i] = path[k, i];
                     path[k, i] = temp;
                 }
             }
             return dist;

         }

 
     }
 }