【数据结构】有向图、无向图以及最短路(Dijkstra, Floyd)算法的C#实现（纯模板Template实现）

有个网友在前面一篇里面留言，要求Floyd算法。这里我实现了两个算法，同时去原有代码进行了一下更新：

  public sealed class GraphVertex<M> { #region Constructor public GraphVertex() { } #endregion #region Fields private Int32 nID = default(Int32); private M objData = default(M); #endregion #region Properties public Int32 ID { get { return nID; } set { nID = value; } } public M Data { get { return objData; } set { objData = value; } } #endregion } public struct GraphEdgeCore : IEquatable<GraphEdgeCore> { public GraphEdgeCore(Int32 i1, Int32 i2) { ID1 = i1; ID2 = i2; } public Int32 ID1; public Int32 ID2; public Boolean IsValidated() { if (ID1 == -1 || ID2 == -1) return false; //if (ID1 == ID2) // return false; return true; } #region IEquatable<GraphEdgeCore> Members public bool Equals(GraphEdgeCore other) { if (ID1 != other.ID1) return false; if (ID2 != other.ID2) return false; return true; } #endregion #region Operators public static Boolean operator == (GraphEdgeCore ec1, GraphEdgeCore ec2) { return ec1.Equals(ec2); } public static Boolean operator != (GraphEdgeCore ec1, GraphEdgeCore ec2) { return !(ec1 == ec2); } #endregion public override int GetHashCode() { return base.GetHashCode(); } public override bool Equals(object obj) { return (this == (GraphEdgeCore)obj); } } public sealed class GraphEdge<N> { #region Constructor public GraphEdge(Int32 n1, Int32 n2, N obj) { edge.ID1 = n1; edge.ID2 = n2; objData = obj; } #endregion #region Fields private GraphEdgeCore edge; private N objData = default(N); #endregion #region Properties public GraphEdgeCore EdgeCore { get { return edge; } } public N Data { get { return objData; } set { objData = value; } } #endregion } //public abstract class ACGraphEdgeWeight<N> : IComparable, IComparable<ACGraphEdgeWeight<N>> //{ // #region Properties // public static N MinimumValue { get; } // public static N MaximumValue { get; } // public N Value { get; } // #endregion // #region Abstract methods // public N AddWeight(N other); // public N SubtractWeight(N other); // public static bool operator == (IACGraphEdgeWeight<N> ge1, IACGraphEdgeWeight<N> ge2); // #endregion //} public abstract class ACGraphEdgeWeightAssistant<N> //: IComparable, IComparable<ACGraphEdgeWeightAssistant<N>> { #region Properties public abstract N MinimumValue { get; } public abstract N MaximumValue { get; } public abstract N ZeroValue { get; } #endregion #region Abstract methods public abstract N Add(N n1, N n2); public abstract N Subtract(N n1, N n2); public abstract Boolean Equals(N n1, N n2); public abstract Int32 Compare(N n1, N n2); public abstract Boolean IsMaximumValue(N nVal); public abstract Boolean IsMinimumValue(N nVal); public abstract Boolean IsZeroValue(N nVal); public abstract KeyValuePair<Int32, N> GetMinimumValue(Dictionary<Int32, N> dictVals); public abstract N GetMinimumValue(List<N> listVals); public abstract N GetMinimumValue(N[] arVals); public abstract KeyValuePair<Int32, N> GetMaximumValue(Dictionary<Int32, N> dictVals); public abstract N GetMaximumValue(List<N> listVals); public abstract N GetMaximumValue(N[] arVals); #endregion //#region IComparable<ACGraphEdgeWeightAssistant<N>> Members //public int CompareTo(ACGraphEdgeWeightAssistant<N> other) //{ // throw new NotImplementedException(); //} //#endregion //#region IComparable Members //public int CompareTo(object obj) //{ // return CompareTo(obj as ACGraphEdgeWeightAssistant<N>); //} //#endregion } public sealed class GraphPath<N> : ICloneable { #region Constructor public GraphPath() { } public GraphPath(GraphPath<N> other) : this() { if (other != null) { nCurID = other.nCurID; curCost = other.curCost; foreach (Int32 n in other.listPath) listPath.Add(n); } } #endregion #region Fields private List<Int32> listPath = new List<Int32>(); private Int32 nCurID = default(Int32); private N curCost = default(N); private Boolean bDeadPath = false; #endregion #region Properties public List<Int32> PathNodes { get { return listPath; } } public Int32 CurrentID { get { return nCurID; } set { nCurID = value; } } public N CurrentCost { get { return curCost; } set { curCost = value; } } public Boolean DeadPath { get { return bDeadPath; } set { bDeadPath = value; } } #endregion #region ICloneable Members public object Clone() { return new GraphPath<N>(this); } #endregion } public sealed class Graph<M, N> // where N : ValueType { #region Constructor public Graph(ACGraphEdgeWeightAssistant<N> objAss) { System.Diagnostics.Debug.Assert(objAss != null); pAssist = objAss; } #endregion #region Fields private Dictionary<Int32, GraphVertex<M>> dictNodes = new Dictionary<int, GraphVertex<M>>(); private List<GraphEdge<N>> listEdges = new List<GraphEdge<N>>(); private Int32 nVertexID = 0; // Assistant for working for N private ACGraphEdgeWeightAssistant<N> pAssist = null; #endregion #region Properties public Int32 NodesAmount { get { return dictNodes.Count; } } public Int32 EdgesAmount { get { return listEdges.Count; } } #endregion #region Public methods public void InsertVertex(GraphVertex<M> objVertex) { System.Diagnostics.Debug.Assert(objVertex != null); objVertex.ID = nVertexID++; dictNodes.Add(objVertex.ID, objVertex); } public void InsertEdge(GraphEdge<N> objEdge) { System.Diagnostics.Debug.Assert(objEdge != null); if (!objEdge.EdgeCore.IsValidated()) return; if (!dictNodes.ContainsKey(objEdge.EdgeCore.ID1)) return; if (!dictNodes.ContainsKey(objEdge.EdgeCore.ID2)) return; listEdges.Add(objEdge); } public GraphEdge<N>[] GetEdges(GraphEdgeCore objEdgeCore) { List<GraphEdge<N>> lists = new List<GraphEdge<N>>(); foreach (GraphEdge<N> ge in listEdges) { if (ge.EdgeCore == objEdgeCore) lists.Add(ge); } return lists.ToArray(); } public GraphEdge<N>[] GetEdges(Int32 nID, Boolean bSource) { List<GraphEdge<N>> lists = new List<GraphEdge<N>>(); foreach (GraphEdge<N> ge in listEdges) { if (bSource) { if (ge.EdgeCore.ID1 == nID) lists.Add(ge); } else { if (ge.EdgeCore.ID2 == nID) lists.Add(ge); } } return lists.ToArray(); } public GraphEdge<N>[] GetAllEdges() { return listEdges.ToArray(); } public GraphVertex<M>[] GetAllVerteics() { List<GraphVertex<M>> listVer = new List<GraphVertex<M>>(); foreach (GraphVertex<M> gv in dictNodes.Values) listVer.Add(gv); return listVer.ToArray(); } public N GetEdgeWeight(Int32 i1, Int32 i2) { foreach (GraphEdge<N> ge in listEdges) { if (ge.EdgeCore.ID1 == i1 || ge.EdgeCore.ID2 == i2) return ge.Data; } return pAssist.MaximumValue; } public void Clear() { dictNodes.Clear(); listEdges.Clear(); nVertexID = 0; } // Get shortest path via Dijkstra method // Note: call this method after you make sure that the weight should not negative. // Key of this method : P-Set and T-Set. each step modify the T set by get the minmium value and fetch it in P set. public void DijkstraShortestPath(Int32 nSource, Int32 nTarget, List<GraphPath<N>> listPaths) { System.Diagnostics.Debug.Assert(listPaths != null); listPaths.Clear(); GraphPath<N> gp = null; if (!dictNodes.ContainsKey(nSource)) return; if (!dictNodes.ContainsKey(nTarget)) return; if (nSource == nTarget) { gp = new GraphPath<N>(); gp.CurrentCost = pAssist.ZeroValue; gp.PathNodes.Add(nSource); listPaths.Add(gp); return; } Dictionary<Int32, N> dictPSet = new Dictionary<Int32, N>(); Dictionary<Int32, N> dictTSet = new Dictionary<Int32, N>(); // Initialize dictPSet.Add(nSource, pAssist.ZeroValue); foreach (Int32 nVer in dictNodes.Keys) { if (nVer != nSource) dictTSet.Add(nVer, pAssist.MaximumValue); } while (!dictPSet.ContainsKey(nTarget)) { // Go through each item in P Set foreach (Int32 nID in dictPSet.Keys) { foreach (GraphEdge<N> ge in GetEdges(nID, true)) { if (dictTSet.ContainsKey(ge.EdgeCore.ID2)) { // Update the T value: min { P(X) + W, T(X) } N nTValue = dictTSet[ge.EdgeCore.ID2]; N nPValue = dictPSet[nID]; N nVal = pAssist.Add(nPValue, ge.Data); if (pAssist.IsMaximumValue(nTValue)) { dictTSet[ge.EdgeCore.ID2] = nVal; } else { if (pAssist.Compare(nTValue, nVal) > 0) { dictTSet[ge.EdgeCore.ID2] = nVal; } } } } } // Get the minimum of TSet Int32 nTID = default(Int32); N ntmp = pAssist.MaximumValue; foreach (KeyValuePair<Int32, N> kvp in dictTSet) { if (pAssist.Compare(kvp.Value, ntmp) < 0) { ntmp = kvp.Value; nTID = kvp.Key; } } if (nTID == default(Int32)) break; dictTSet.Remove(nTID); dictPSet.Add(nTID, ntmp); } // OKay, we get the final result, parse the result out gp = new GraphPath<N>(); gp.CurrentID = nTarget; gp.CurrentCost = dictPSet[nTarget]; gp.PathNodes.Add(nTarget); listPaths.Add(gp); Boolean bEnd = false; Boolean bExisted = false; List<GraphPath<N>> listTempPaths = new List<GraphPath<N>>(); while (!bEnd) { bExisted = false; listTempPaths.Clear(); foreach (GraphPath<N> gpath in listPaths) { if (gpath.DeadPath) continue; foreach (GraphEdge<N> ge in GetEdges(gpath.CurrentID, false)) { //dictPSet[ge.Data] if (dictPSet.ContainsKey(ge.EdgeCore.ID1) && pAssist.Compare(gpath.CurrentCost, pAssist.Add(ge.Data, dictPSet[ge.EdgeCore.ID1])) == 0) { if (!bExisted) { gpath.CurrentID = ge.EdgeCore.ID1; gpath.PathNodes.Add(ge.EdgeCore.ID1); gpath.CurrentCost = dictPSet[ge.EdgeCore.ID1]; bExisted = true; } else { // Existed already in current GraphPath<N> gp2 = new GraphPath<N>(gpath); gp2.CurrentID = ge.EdgeCore.ID1; gp2.PathNodes.Add(ge.EdgeCore.ID1); gp2.CurrentCost = dictPSet[ge.EdgeCore.ID1]; listTempPaths.Add(gp2); } } } if (!bExisted) { gpath.DeadPath = true; } } foreach (GraphPath<N> gpath in listTempPaths) listPaths.Add(gpath); foreach (GraphPath<N> gpath in listPaths) { if ((!gpath.DeadPath) && gpath.PathNodes.Contains(nSource)) { bEnd = true; break; } } } // Finalize the result output foreach (GraphPath<N> gpth in listPaths) { if (gpth.DeadPath) listPaths.Remove(gpth); else gpth.CurrentCost = dictPSet[nTarget]; } } // Get shortest path : Floyd method // Note: Floyd method actually searches all shortest path from one starting vertex // Key of this method: Workout D-table until two generation of D-column are the same public void FloydShortestPath(Int32 nSource, Int32 nTarget, List<GraphPath<N>> listPaths) { System.Diagnostics.Debug.Assert(listPaths != null); listPaths.Clear(); GraphPath<N> gp = null; Dictionary<Int32, Int32> dictIDIdxMap = new Dictionary<Int32, Int32>(); if (!dictNodes.ContainsKey(nSource)) return; if (!dictNodes.ContainsKey(nTarget)) return; if (nSource == nTarget) { gp = new GraphPath<N>(); gp.CurrentCost = pAssist.MinimumValue; gp.PathNodes.Add(nSource); listPaths.Add(gp); return; } // Adjustment tables N[,] arAdj = new N[dictNodes.Count, dictNodes.Count]; System.Diagnostics.Debug.Assert(arAdj != null); List<N[]> listDTables = new List<N[]>(); System.Diagnostics.Debug.Assert(listDTables != null); Int32 nGen = 0; Boolean bEnd = false; // Build the maping between ID and index Int32[] arIDs = new Int32[dictNodes.Count]; dictNodes.Keys.CopyTo(arIDs, 0); Int32 nIdx = 1; foreach (Int32 i in dictNodes.Keys) { if (i != nSource) arIDs[nIdx++] = i; } arIDs[0] = nSource; nIdx = 0; foreach (Int32 i in arIDs) dictIDIdxMap.Add(i, nIdx++); // Workout the adjustment table for (Int32 i = 0; i < dictNodes.Count; ++i) { for (Int32 j = 0; j < dictNodes.Count; ++j) arAdj[i, j] = pAssist.MaximumValue; } foreach (GraphEdge<N> ge in listEdges) { // Modifiy adjustment if (pAssist.Compare(ge.Data, arAdj[ge.EdgeCore.ID1, ge.EdgeCore.ID2]) < 0) { arAdj[dictIDIdxMap[ge.EdgeCore.ID1], dictIDIdxMap[ge.EdgeCore.ID2]] = ge.Data; } } // Initialize value of D table N[] nVal = new N[dictIDIdxMap.Count]; System.Diagnostics.Debug.Assert(nVal != null); N[] nTmp = new N[dictIDIdxMap.Count]; System.Diagnostics.Debug.Assert(nTmp != null); for (Int32 i = 0; i < dictIDIdxMap.Count; ++i) nVal[i] = arAdj[0, i]; listDTables.Add(nVal); while (!bEnd) { nGen++; nVal = new N[dictIDIdxMap.Count]; System.Diagnostics.Debug.Assert(nVal != null); for (Int32 i = 0; i < dictIDIdxMap.Count; ++i) { for (Int32 j = 0; j < dictIDIdxMap.Count; ++j) { // For each node j, the value is min { D(nGen - 1) + V(i, j) } N n1 = listDTables[nGen - 1][j]; N n2 = arAdj[j, i]; if (pAssist.IsMaximumValue(n1) || pAssist.IsMaximumValue(n2)) nTmp[j] = pAssist.MaximumValue; else nTmp[j] = pAssist.Add(n1, n2); } nVal[i] = pAssist.GetMinimumValue(nTmp); } listDTables.Add(nVal); // Check whether should stop. N[] d1 = listDTables[nGen - 1]; Boolean bBreaked = false; for (Int32 i = 0; i < dictIDIdxMap.Count; ++i) { if (pAssist.Compare(d1[i], nVal[i]) != 0) { bBreaked = true; break; } } if (!bBreaked) bEnd = true; } // Get the final result out listDTables.RemoveAt(nGen --); //Int32 nTargetIdx = dictIDIdxMap[nTarget]; //nIdx = nTargetIdx; Boolean bExisted = false; List<GraphPath<N>> listTempPaths = new List<GraphPath<N>>(); gp = new GraphPath<N>(); gp.CurrentID = nTarget; gp.CurrentCost = listDTables[nGen][dictIDIdxMap[nTarget]]; gp.PathNodes.Add(nTarget); listPaths.Add(gp); while (nGen > 0) { bExisted = false; listTempPaths.Clear(); foreach (GraphPath<N> gpath in listPaths) { if (gpath.DeadPath) continue; for (Int32 j = 0; j < dictIDIdxMap.Count; ++j) { // For each node j, the value is min { D(nGen - 1) + V(i, j) } N n1 = listDTables[nGen - 1][j]; N n2 = arAdj[j, dictIDIdxMap[gpath.CurrentID]]; if (pAssist.IsMaximumValue(n1) || pAssist.IsMaximumValue(n2)) nTmp[j] = pAssist.MaximumValue; else nTmp[j] = pAssist.Add(n1, n2); } for(Int32 j = 0; j < nTmp.Length; ++ j) { if (pAssist.Compare(nTmp[j], gpath.CurrentCost) == 0) { if (!bExisted) { gpath.CurrentID = dictIDIdxMap[j]; gpath.PathNodes.Add(gpath.CurrentID); gpath.CurrentCost = listDTables[nGen][j]; bExisted = true; } else { // Existed already in current GraphPath<N> gp2 = new GraphPath<N>(gpath); gpath.CurrentID = dictIDIdxMap[j]; gpath.PathNodes.Add(gpath.CurrentID); gpath.CurrentCost = listDTables[nGen][j]; listTempPaths.Add(gp2); } } } if (!bExisted) { gpath.DeadPath = true; } } foreach (GraphPath<N> gpath in listTempPaths) listPaths.Add(gpath); nGen--; } // Finalize the result output foreach (GraphPath<N> gpth in listPaths) { if (gpth.DeadPath) listPaths.Remove(gpth); else { if (!gpth.PathNodes.Contains(nSource)) gpth.PathNodes.Add(nSource); gpth.CurrentID = default(Int32); gpth.CurrentCost = listDTables[listDTables.Count - 1][dictIDIdxMap[nTarget]]; } } //while (nGen >= 0) //{ // // Roll back // for (Int32 i = 0; i < dictIDIdxMap.Count; ++i) // { // for (Int32 j = 0; j < dictIDIdxMap.Count; ++j) // { // // For each node j, the value is min { D(nGen - 1) + V(i, j) } // N n1 = listDTables[nGen - 1][j]; // N n2 = arAdj[j, i]; // if (pAssist.IsMaximumValue(n1) || pAssist.IsMaximumValue(n2)) // nTmp[j] = pAssist.MaximumValue; // else // nTmp[j] = pAssist.Add(n1, n2); // } // nVal[i] = pAssist.GetMinimumValue(nTmp); // } // foreach (N nv in nVal) // { // if (pAssist.Compare(nv, listDTables[nGen][nIdx]) == 0) // { // } // } // nGen--; //} } #endregion }

 

测试代码：

首先派生Assistance类

public sealed class ACGraphEdgeWeightSingleAssistant : ACGraphEdgeWeightAssistant<Single> { public override Single MinimumValue { get { return Single.MinValue; } } public override float ZeroValue { get { return 0; } } public override Single MaximumValue { get { return Single.MaxValue; } } public override float Add(float n1, float n2) { return n1 + n2; } public override float Subtract(float n1, float n2) { return n1 - n2; } public override bool Equals(float n1, float n2) { return n1 == n2; } public override int Compare(float n1, float n2) { if (n1 > n2) return 1; if (n1 < n2) return -1; return 0; } public override bool IsMaximumValue(Single nVal) { return nVal == Single.MaxValue; } public override bool IsMinimumValue(Single nVal) { return nVal == Single.MinValue; } public override bool IsZeroValue(Single nVal) { return nVal == 0.0f; } public override KeyValuePair<Int32, Single> GetMinimumValue(Dictionary<Int32, Single> dictVals) { System.Diagnostics.Debug.Assert(dictVals != null); KeyValuePair<Int32, Single> kvpTmp = default(KeyValuePair<Int32, Single>); Boolean bFirst = true; foreach (KeyValuePair<Int32, Single> kvp in dictVals) { if (bFirst) { kvpTmp = new KeyValuePair<Int32, Single>(kvp.Key, kvp.Value); bFirst = false; continue; } if (kvp.Value < kvpTmp.Value) { kvpTmp = new KeyValuePair<Int32, Single>(kvp.Key, kvp.Value); continue; } } return kvpTmp; } public override Single GetMinimumValue(List<Single> listVals) { System.Diagnostics.Debug.Assert(listVals != null); Single sTmp = default(Single); Boolean bFirst = true; foreach (Single sg in listVals) { if (bFirst) { sTmp = sg; bFirst = false; continue; } if (sg < sTmp) { sTmp = sg; continue; } } return sTmp; } public override Single GetMinimumValue(Single[] arVals) { System.Diagnostics.Debug.Assert(arVals != null); Single sTmp = default(Single); Boolean bFirst = true; foreach (Single sg in arVals) { if (bFirst) { sTmp = sg; bFirst = false; continue; } if (sg < sTmp) { sTmp = sg; continue; } } return sTmp; } public override KeyValuePair<Int32, Single> GetMaximumValue(Dictionary<Int32, Single> dictVals) { System.Diagnostics.Debug.Assert(dictVals != null); KeyValuePair<Int32, Single> kvpTmp = default(KeyValuePair<Int32, Single>); Boolean bFirst = true; foreach (KeyValuePair<Int32, Single> kvp in dictVals) { if (bFirst) { kvpTmp = new KeyValuePair<Int32, Single>(kvp.Key, kvp.Value); bFirst = false; continue; } if (kvp.Value > kvpTmp.Value) { kvpTmp = new KeyValuePair<Int32, Single>(kvp.Key, kvp.Value); continue; } } return kvpTmp; } public override Single GetMaximumValue(List<Single> listVals) { System.Diagnostics.Debug.Assert(listVals != null); Single sTmp = default(Single); Boolean bFirst = true; foreach (Single sg in listVals) { if (bFirst) { sTmp = sg; bFirst = false; continue; } if (sg > sTmp) { sTmp = sg; continue; } } return sTmp; } public override Single GetMaximumValue(Single[] arVals) { System.Diagnostics.Debug.Assert(arVals != null); Single sTmp = default(Single); Boolean bFirst = true; foreach (Single sg in arVals) { if (bFirst) { sTmp = sg; bFirst = false; continue; } if (sg > sTmp) { sTmp = sg; continue; } } return sTmp; } }

然后，进行计算(Floyd)：

GraphVertex<Char> gv = new GraphVertex<Char>(); ACGraphEdgeWeightSingleAssistant objWSA = new ACGraphEdgeWeightSingleAssistant(); Dictionary<Char, Int32> dictVer = new Dictionary<Char, Int32>(); Graph<Char, Single> gph = new Graph<Char, Single>(objWSA); List<GraphPath<Single>> listPaths = new List<GraphPath<Single>>(); gv.Data = '1'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '2'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '3'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '4'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '5'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '6'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '7'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); gv = new GraphVertex<char>(); gv.Data = '8'; gph.InsertVertex(gv); dictVer.Add(gv.Data, gv.ID); GraphEdge<Single> ge = new GraphEdge<float>(dictVer['1'], dictVer['2'], -1); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['1'], dictVer['3'], -2); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['1'], dictVer['4'], 3); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['2'], dictVer['1'], 6); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['2'], dictVer['5'], 2); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['3'], dictVer['2'], -3); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['3'], dictVer['4'], -5); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['3'], dictVer['6'], 1); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['4'], dictVer['1'], 8); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['4'], dictVer['7'], 2); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['5'], dictVer['2'], -1); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['6'], dictVer['5'], 1); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['6'], dictVer['7'], 1); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['6'], dictVer['8'], 7); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['7'], dictVer['4'], -1); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['8'], dictVer['5'], -3); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['8'], dictVer['7'], -5); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['1'], dictVer['1'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['2'], dictVer['2'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['3'], dictVer['3'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['4'], dictVer['4'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['5'], dictVer['5'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['6'], dictVer['6'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['7'], dictVer['7'], 0); gph.InsertEdge(ge); ge = new GraphEdge<float>(dictVer['8'], dictVer['8'], 0); gph.InsertEdge(ge); gph.FloydShortestPath(dictVer['1'], dictVer['8'], listPaths);