大家好，我是小鸭酱，博客地址为：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);
}
}
}