using System; using System.Collections.Generic; using System.IO; namespace TravelSmart { class Graph { List<string> cities = new List<string>(); private int[,] cost = new int[10, 10]; private int n = 0; int infinity = 9999999; public List<string> Cities { get { return cities; } } public int getIndex(string vname) { for (int i = 0; i < n; i++) if (cities[i].Trim() == vname) return (i); return (-1); } public Graph() { for (int row = 0; row < n; row++) for (int col = 0; col < n; col++) cost[row, col] = infinity; StreamReader reader1 = new StreamReader("Cities.txt"); string line; while ((line = reader1.ReadLine()) != null) cities.Add(line); n = cities.Count; reader1.Close(); } public string findShortestPath(string source, string destination) { string result=""; int[] Distance = new int[10]; bool[] Final = new bool[10]; StreamReader reader = new StreamReader("Routs.txt"); string lines = ""; char[] separator = { '|' }; while ((lines = reader.ReadLine()) != null) { string[] route = lines.Split(separator); source = route[0]; int row = getIndex(source); destination = route[1]; int col = getIndex(destination); int distance = Convert.ToInt32(route[2]); cost[row, col] = distance; //Initialize Distance Array for (int i = 0; i < n; i++) Distance[i] = cost[row, i]; Final[row] = true; } reader.Close(); for (int row = 1; row < n; row++)//n-1 passes { int v = 0; for (int col= 0; col < n; col++) { if (Final[col] == false) { v = col; break; } } for (int col = 0; col < n; col++) { if ((Final[col] == false) && (Distance[col] < Distance[v])) v = col; } Final[v] = true; for (int w = 0; w < n; w++) { if (Final[w] == false) { if (Distance[v] + cost[v, w] < Distance[w]) Distance[w] = Distance[v] + cost[v, w]; } } } for (int col = 0; col < n; col++) { if (Distance[col] == infinity) { result = source + "->" + destination + "=" + Distance[col] + " = No path"; } else { result = source + "->" + destination + "=" + Distance[col] + " KM"; } } return result; } private void showMatrix() { for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) if ((cost[row, col] != 0) && (cost[row, col] != infinity)) { Console.Write(" " + cost[row, col]); } Console.WriteLine(); } } } }
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)