Dijkstra算法C#实现及其布线运用

大家好,我是小鸭酱,博客地址为:http://www.cnblogs.com/xiaoyajiang

以下是空调布线对Dijkstra算法的运用,采用C#实现。

问题:室内机多台,室外机一台。寻找室内机到室外机的最短路径

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Windows;
 
namespace shortestPath
{
    class Program
    {
        const double INF = 429496729;//无路径时的权值
        //--------------------------------------------------------------------------------*
        //函数名: Dijkstra                                                                                *
        //功  能: 找出室内机组和室外机的最短路径(室内机室外机均指投影到最近的墙上的点)*
        //参  数: cost   : List<List<double>>类型                                                     *
        //        n:   int型   所有不重合节点个数,也是cost矩阵的阶                                     *
        //        v:   int型   室内机的标号                                                                *
        //        terminals:   List<int>型  许多室外机的标号                                      *
        //返  回:List<List<int>>类型  每行均为 每个室内机 → 室外机的路径                        *
        //作  者:小鸭酱的书签                                                                          *
        //时  间:2016年3月28日                                                                     *
        //修改时间:                                                                                  *
        //---------------------------------------------------------------------------------*
        static List<List<int>> Dijkstra(List<List<double>> cost, int n, int v, List<int> terminals)
        {
            List<List<int>> allRoutes = new List<List<int>>();//保存所有路径
 
            List<double> dist = new List<double>();
            List<int> s = new List<int>();
            List<int> path = new List<int>();
            double mindis;
            int i, j, u, pre;
            for (i = 0; i < n; i++)
            {
                dist.Add(cost[v][i]);
                s.Add(0);
 
                if (cost[v][i] < INF)
                    path.Add(v);
                else
                    path.Add(-1);
            }
 
            s[v] = 1; //室外机编号v放入s中
            path[v] = 0;
            //循环直到所有顶点的最短路径都求出
            for (i = 0; i < n; i++)
            {
                mindis = INF;
                u = -1;
                for (j = 0; j < n; j++) //选取不在s中且具有最小距离的顶点u
                {
                    if (s[j] == 0 && dist[j] < mindis)
                    {
                        u = j;
                        mindis = dist[j];
                    }
                }
 
                if (u != -1) //找到最小距离的顶点u
                {
                    s[u] = 1; //顶点u加入s中
                    for (j = 0; j < n; j++) //修改不在s中的顶点距离
                    {
                        if (s[j] == 0)
                        {
                            if (cost[u][j] < INF && dist[u] + cost[u][j] < dist[j])
                            {
                                dist[j] = dist[u] + cost[u][j];//修改源点到vj的距离
                                path[j] = u;//保存当前最短路径中的前一个顶点编号
                            }
                        }
                    }
                }
            }
 
            //从室内机到室外机的最短路径
            int index = 0;
            for (i = 0; i < n; i++)
            {
                if (i != v)
                {
                    if (s[i] == 1)
                    {
                        List<int> route = new List<int>();
                        pre = i;
                        while (pre != v) //直到求解到初始顶点
                        {
                            if (index < terminals.Count())
                            {
                                if (terminals[index] == i)
                                {
                                    route.Add(pre);
                                }
                            }
                            pre = path[pre];
                        }
                        if (index < terminals.Count())
                        {
                            if (terminals[index] == i)
                            {
                                route.Add(pre);
                            }
                        }
                        if (index < terminals.Count())
                        {
                            if (terminals[index] == i)
                            {
                                allRoutes.Add(route);
                                index++;
                                if (index == terminals.Count())
                                    return allRoutes;
                            }
                        }
                    }
                }
            }
            return allRoutes;
        }
        static void Main(string[] args)  // test
        {
            List<List<double>> cost = new List<List<double>>();
            List<double> l1 = new List<double>() {INF,5,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,INF,INF};//1
            List<double> l2 = new List<double>() {5,INF,INF,INF,INF,2,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,4,INF};//1
            List<double> l3 = new List<double>() {INF,INF,INF,5,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1,2};//1
            List<double> l4 = new List<double>() {INF,INF,5,INF,INF,INF,INF,INF,INF,5,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l5 = new List<double>() {INF,INF,INF,INF,INF,5,INF,INF,INF,INF,INF,INF,INF,INF,10,INF,INF,INF,INF,INF,INF,1,INF,INF};//1
            List<double> l6 = new List<double>() {INF,2,INF,INF,5,INF,3,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l7 = new List<double>() {INF,INF,INF,INF,INF,3,INF,5,INF,INF,2,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l8 = new List<double>() {INF,INF,INF,INF,INF,INF,5,INF,5,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,3};//1
            List<double> l9 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,3,INF,2,INF,INF,2,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l10 = new List<double>() {INF,INF,INF,5,INF,INF,INF,INF,2,INF,INF,INF,INF,2,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l11 = new List<double>() {INF,INF,INF,INF,INF,INF,2,INF,INF,INF,INF,4,INF,INF,INF,5,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l12 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,4,INF,4,INF,INF,INF,5,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l13 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,2,INF,INF,4,INF,2,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l14 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,2,INF,INF,2,INF,INF,INF,INF,5,INF,INF,INF,INF,INF,INF};//1
            List<double> l15 = new List<double>() {INF,INF,INF,INF,10,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,2,INF,INF,INF};//1
            List<double> l16 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,5,INF,INF,INF,INF,INF,4,INF,INF,INF,3,INF,INF,INF};//1
            List<double> l17 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,5,INF,INF,INF,4,INF,6,INF,2,INF,INF,INF,INF};//1
            List<double> l18 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,5,INF,INF,6,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l19 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,8,2,INF,INF,INF};//1
            List<double> l20 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,2,INF,8,INF,INF,INF,INF,INF};//1
            List<double> l21 = new List<double>() {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,2,3,INF,INF,2,INF,INF,INF,INF,INF};//1
            List<double> l22 = new List<double>() {1,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l23 = new List<double>() {INF,4,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            List<double> l24 = new List<double>() {INF,INF,2,INF,INF,INF,INF,3,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};//1
            cost.Add(l1);
            cost.Add(l2);
            cost.Add(l3);
            cost.Add(l4);
            cost.Add(l5);
            cost.Add(l6);
            cost.Add(l7);
            cost.Add(l8);
            cost.Add(l9);
            cost.Add(l10);
            cost.Add(l11);
            cost.Add(l12);
            cost.Add(l13);
            cost.Add(l14);
            cost.Add(l15);
            cost.Add(l16);
            cost.Add(l17);
            cost.Add(l18);
            cost.Add(l19);
            cost.Add(l20);
            cost.Add(l21);
            cost.Add(l22);
            cost.Add(l23);
            cost.Add(l24);
 
            List<int> terminals = new List<int>(){22,23};
 
 
            int v = 21;
 
            List<List<int>> result = new List<List<int>>();
 
        result = Dijkstra(cost, 24, v, terminals);
        }
    }
}
上一篇:VC++6.0使用OpenGL前的配置(必看)


下一篇:PHP调试工具Xdebug安装配置教程