最短路径Dijkstra

程序采用迪杰特拉斯（Dijkstra）算法求解带权值的有向图中从某个起始节点到其它节点的最短路径。 开发环境：vs2013，.NET4.0

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 最短路径Dijkstra
{
class DijkstraSolution
{
    /*
        * 求解各节点最短路径，获取path，和cost数组，
        * path[i]表示vi节点的前继节点索引，一直追溯到起点。
        * cost[i]表示vi节点的花费
        */
    public static void FindShortestPath（int[] graphint startIndex int[] path int[] costint max）
    {
        int nodeCount = graph.GetLength（0）;
        bool[] v = new bool[nodeCount];
        //初始化 path，cost，V
        for （int i = 0; i         {
            if （i == startIndex）//如果是出发点
            {
                v[i] = true;//
            }
            else
            {
                cost[i] = graph[startIndexi ];
                if （cost[i] < max） path[i] = startIndex;
                else path[i] = -1;
                v[i] = false;
            }
        }
        //
        for（int i=1;i        {
            int minCost = max ;
            int curNode=-1;
            for （int w = 0; w < nodeCount; w++）
            {
                if （!v[w]）//未在V集合中
                { 
                    if（cost[w]                    {
                        minCost = cost[w];
                        curNode = w;
                    }
                }
            }//for  获取最小权值的节点
            if （curNode == -1） break;//剩下都是不可通行的节点，跳出循环
            v[curNode] = true;
            for （int w = 0; w < nodeCount; w++）
            {
                if （!v[w] && （graph[curNode w] + cost[curNode] < cost[w]））
                {
                    cost[w] = graph[curNode w] + cost[curNode];//更新权值
                    path[w] = curNode;//更新路径
                }
            }//for 更新其他节点的权值（距离）和路径
        }//
    }
}
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      18668  2016-10-18 15:46  最短路径Dijkstra\最短路径Dijkstra\bin\Debug\0.png

     文件      25088  2016-10-18 17:17  最短路径Dijkstra\最短路径Dijkstra\bin\Debug\最短路径Dijkstra.exe

     文件      28160  2016-10-18 17:17  最短路径Dijkstra\最短路径Dijkstra\bin\Debug\最短路径Dijkstra.pdb

     文件      24216  2016-10-18 17:22  最短路径Dijkstra\最短路径Dijkstra\bin\Debug\最短路径Dijkstra.vshost.exe

     文件        490  2015-07-10 19:01  最短路径Dijkstra\最短路径Dijkstra\bin\Debug\最短路径Dijkstra.vshost.exe.manifest

     文件       2049  2016-10-18 17:17  最短路径Dijkstra\最短路径Dijkstra\DijkstraSolution.cs

     文件       1644  2016-10-18 17:17  最短路径Dijkstra\最短路径Dijkstra\Form1.cs

     文件       5524  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\Form1.Designer.cs

     文件       6909  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\Form1.resx

     文件        865  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\DesignTimeResolveAssemblyReferences.cache

     文件       6959  2016-10-18 16:01  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\DesignTimeResolveAssemblyReferencesInput.cache

     文件       4608  2016-10-18 15:47  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\TempPE\Properties.Resources.Designer.cs.dll

     文件        890  2016-10-18 17:22  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.csproj.FileListAbsolute.txt

     文件       1012  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.csproj.GenerateResource.Cache

     文件       2211  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.csprojResolveAssemblyReference.cache

     文件      25088  2016-10-18 17:17  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.exe

     文件        180  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.Form1.resources

     文件      28160  2016-10-18 17:17  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.pdb

     文件      13453  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\最短路径Dijkstra.Properties.Resources.resources

     文件        501  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra\Program.cs

     文件       1364  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra\Properties\AssemblyInfo.cs

     文件       3241  2016-10-18 15:47  最短路径Dijkstra\最短路径Dijkstra\Properties\Resources.Designer.cs

     文件       6189  2016-10-18 15:47  最短路径Dijkstra\最短路径Dijkstra\Properties\Resources.resx

     文件       1107  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra\Properties\Settings.Designer.cs

     文件        249  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra\Properties\Settings.settings

     文件       3909  2016-10-18 16:53  最短路径Dijkstra\最短路径Dijkstra\最短路径Dijkstra.csproj

     文件       1029  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra.sln

    ..A..H.     11776  2016-10-18 15:45  最短路径Dijkstra\最短路径Dijkstra.v12.suo

     目录          0  2016-10-18 17:28  最短路径Dijkstra\最短路径Dijkstra\obj\Debug\TempPE

     目录          0  2016-10-18 17:28  最短路径Dijkstra\最短路径Dijkstra\bin\Debug

............此处省略9个文件信息