我正在开发一个程序,我必须找到 12 个城市之间的最短路径,从西雅图开始,到迈阿密结束。我正在使用 Dijkstra 的算法,因为路径是加权的。这是我的代码到目前为止,这一切都可以工作,除了我得到的答案不是我需要的答案,尽管它是正确的。
这部分代码设置了所有内容，并创建了排序算法。
class Graph
{
Dictionary<string, Dictionary<string, int>> vertices = new Dictionary<string, Dictionary<string, int>>();
public void add_vertex(string name, Dictionary<string, int> edges)
{
vertices[name] = edges;
}
public List<string> shortest_path(string start, string finish)
{
var previous = new Dictionary<string, string>();
var distances = new Dictionary<string, int>();
var nodes = new List<string>();
List<string> path = null;
foreach (var vertex in vertices)
{
if (vertex.Key == start)
{
distances[vertex.Key] = 1;
}
else
{
distances[vertex.Key] = int.MaxValue;
}
nodes.Add(vertex.Key);
}
while (nodes.Count != 0)
{
nodes.Sort((x, y) => distances[x] - distances[y]);
var smallest = nodes[0];
nodes.Remove(smallest);
if (smallest == finish)
{
path = new List<string>();
while (previous.ContainsKey(smallest))
{
path.Add(smallest);
smallest = previous[smallest];
}
break;
}
if (distances[smallest] == int.MaxValue)
{
break;
}
foreach (var neighbor in vertices[smallest])
{
var alt = distances[smallest] + neighbor.Value;
if (alt < distances[neighbor.Key])
{
distances[neighbor.Key] = alt;
previous[neighbor.Key] = smallest;
}
}
}
return path;
}
}
下面是我创建“城市”以及创建它们之间的价值的地方。
class MainClass
{
public static void Main(string[] args)
{
Graph g = new Graph();
g.add_vertex("Seattle", new Dictionary<string, int>() { {"San Francisco", 1306}, {"Denver", 2161}, {"Minneapolis", 2661} });
g.add_vertex("San Francisco", new Dictionary<string, int>() { {"Seattle", 1306}, {"Las Vegas", 919}, {"Los Angeles", 629} });
g.add_vertex("Las Vegas", new Dictionary<string, int>() { {"San Francisco", 919}, {"Los Angeles", 435}, {"Denver", 1225}, {"Dallas", 1983} });
g.add_vertex("Los Angeles", new Dictionary<string, int>() { {"San Francisco", 629}, {"Las Vegas", 435} });
g.add_vertex("Denver", new Dictionary<string, int>() { {"Seattle", 2161}, {"Las Vegas", 1225}, {"Minneapolis", 1483}, {"Dallas", 1258} });
g.add_vertex("Minneapolis", new Dictionary<string, int>() { {"Seattle", 2661}, {"Denver", 1483}, {"Dallas", 1532}, {"Chicago", 661} });
g.add_vertex("Dallas", new Dictionary<string, int>() { {"Las Vegas", 1983}, {"Denver", 1258}, {"Minneapolis", 1532}, {"Washington DC", 2113} });
g.add_vertex("Chicago", new Dictionary<string, int>() { {"Minneapolis", 661}, {"Washington DC", 1145}, {"Boston", 1613} });
g.add_vertex("Washington DC", new Dictionary<string, int>() { {"Dallas", 2113}, {"Chicago", 1145}, {"Boston", 725}, {"New York", 383}, {"Miami", 1709} });
g.add_vertex("Boston", new Dictionary<string, int>() { {"Chicago", 1613}, {"Washington DC", 725}, {"New York", 338} });
g.add_vertex("New York", new Dictionary<string, int>() { {"Washington DC", 383}, {"Boston", 338}, {"Miami", 2145} });
g.add_vertex("Miami", new Dictionary<string, int>() { {"Dallas", 2161}, {"Washington DC", 1709}, {"New York", 2145} });
g.shortest_path("Miami", "Seattle").ForEach(x => Console.Write(x + " > "));
}
}
我需要帮助弄清楚的部分是，当我运行该程序时，我得到：西雅图 ＆ gt;丹佛 ＆ gt;达拉斯。这个答案对于到迈阿密的最短距离是正确的，但是我需要到每个城市的最短距离，而不仅仅是迈阿密。我只是不知道需要更改什么才能正确显示。
3
根据我的理解，提供的代码实现了Dijkstra's Algorithm，修改为一旦某个期望的目标节点被选择到已知从初始节点开始的最短路径的节点集合中就终止。Dijkstra 的算法解决了所谓的Single Source Shortest Path问题。这意味着可以指定某个初始节点，在这种情况下 相反，如果您需要从Miami，并且所需的结果不是由最短的
Miami到所有其他城市的最短路径，请修改实现not以尽早中断循环并删除第二个参数。
1
The line
g.shortest_path("Miami", "Seattle").ForEach(x => Console.Write(x + " > "));
是您指定"Miami"的端点并将输出写入控制台的位置。
您需要在该行周围创建一个循环，指定所需的每个端点
foreach(var endpoint in validEndpoints) {
g.shortest_path(endpoint, "Seattle").ForEach(x => Console.Write(x + " > "));
}
这将是缓慢的，有些事情你可以做，如记忆化来加快它，但至少应该产生你想要的输出。
0
我多年来一直在发布这个代码。你需要一个递归算法。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
//this one uses strings as node names
Dijkstra1.Program.Dijkstra();
//this one uses integers as node names
Dijkstra2.Program.Dijkstra();
}
}
}
namespace Dijkstra1
{
class Program
{
//A connected to B
//B connected to A, C , D
//C connected to B, D
//D connected to B, C , E
//E connected to D.
static List<List<String>> input1 = new List<List<string>>{
new List<String>() {"A","0","1","0","0","0"},
new List<String>() {"B","1","0","1","1","0"},
new List<String>() {"C","0","1","0","1","0"},
new List<String>() {"D","0","1","1","0","1"},
new List<String>() {"E","0","0","0","1","0"}
};
//A | 0 1 2 2 3 |
//B | 1 0 1 1 2 |
//C | 2 1 0 1 2 |
//D | 2 1 1 0 1 |
//E | 3 2 2 1 0 |
static List<List<String>> input2 = new List<List<string>>{
new List<String>() {"A","0","1","2","2","3"},
new List<String>() {"B","1","0","1","1","2"},
new List<String>() {"C","2","1","0","1","2"},
new List<String>() {"D","2","1","1","0","1"},
new List<String>() {"E","3","2","2","1","0"}
};
static public void Dijkstra()
{
CGraph cGraph;
cGraph = new CGraph(input1);
Console.WriteLine("-------------Input 1 -------------");
cGraph.PrintGraph();
cGraph = new CGraph(input2);
Console.WriteLine("-------------Input 2 -------------");
cGraph.PrintGraph();
}
class CGraph
{
List<Node> graph = new List<Node>();
public CGraph(List<List<String>> input)
{
foreach (List<string> inputRow in input)
{
Node newNode = new Node();
newNode.name = inputRow[0];
newNode.distanceDict = new Dictionary<string, Path>();
newNode.visited = false;
newNode.neighbors = new List<Neighbor>();
//for (int index = 1; index < inputRow.Count; index++)
//{
// //skip diagnol values so you don't count a nodes distance to itself.
// //node count start at zero
// // index you have to skip the node name
// //so you have to subtract one from the index
// if ((index - 1) != nodeCount)
// {
// string nodeName = input[index - 1][0];
// int distance = int.P(inputRow[index]);
// newNode.distanceDict.Add(nodeName, new List<string>() { nodeName });
// }
//}
graph.Add(newNode);
}
//initialize neighbors using predefined dictionary
for (int nodeCount = 0; nodeCount < graph.Count; nodeCount++)
{
for (int neighborCount = 0; neighborCount < graph.Count; neighborCount++)
{
//add one to neighbor count to skip Node name in index one
if (input[nodeCount][neighborCount + 1] != "0")
{
Neighbor newNeightbor = new Neighbor();
newNeightbor.node = graph[neighborCount];
newNeightbor.distance = int.P(input[nodeCount][neighborCount + 1]);
graph[nodeCount].neighbors.Add(newNeightbor);
Path path = new Path();
path.nodeNames = new List<string>() { input[neighborCount][0] };
//add one to neighbor count to skip Node name in index one
path.totalDistance = int.P(input[nodeCount][neighborCount + 1]);
graph[nodeCount].distanceDict.Add(input[neighborCount][0], path);
}
}
}
foreach (Node node in graph)
{
foreach (Node nodex in graph)
{
node.visited = false;
}
TransverNode(node);
}
}
public class Neighbor
{
public Node node { get; set; }
public int distance { get; set; }
}
public class Path
{
public List<string> nodeNames { get; set; }
public int totalDistance { get; set; }
}
public class Node
{
public string name { get; set; }
public Dictionary<string, Path> distanceDict { get; set; }
public Boolean visited { get; set; }
public List<Neighbor> neighbors { get; set; }
}
static void TransverNode(Node node)
{
if (!node.visited)
{
node.visited = true;
foreach (Neighbor neighbor in node.neighbors)
{
TransverNode(neighbor.node);
string neighborName = neighbor.node.name;
int neighborDistance = neighbor.distance;
//compair neighbors dictionary with current dictionary
//update current dictionary as required
foreach (string key in neighbor.node.distanceDict.Keys)
{
if (key != node.name)
{
int neighborKeyDistance = neighbor.node.distanceDict[key].totalDistance;
if (node.distanceDict.ContainsKey(key))
{
int currentDistance = node.distanceDict[key].totalDistance;
if (neighborKeyDistance + neighborDistance < currentDistance)
{
List<string> nodeList = new List<string>();
nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);
nodeList.Insert(0, neighbor.node.name);
node.distanceDict[key].nodeNames = nodeList;
node.distanceDict[key].totalDistance = neighborKeyDistance + neighborDistance;
}
}
else
{
List<string> nodeList = new List<string>();
nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);
nodeList.Insert(0, neighbor.node.name);
Path path = new Path();
path.nodeNames = nodeList;
path.totalDistance = neighbor.distance + neighborKeyDistance;
node.distanceDict.Add(key, path);
}
}
}
}
}
}
public void PrintGraph()
{
foreach (Node node in graph)
{
Console.WriteLine("Node : {0}", node.name);
foreach (string key in node.distanceDict.Keys.OrderBy(x => x))
{
Console.WriteLine(" Distance to node {0} = {1}, Path : {2}", key, node.distanceDict[key].totalDistance, string.Join(",", node.distanceDict[key].nodeNames.ToArray()));
}
}
}
}
}
}
namespace Dijkstra2
{
class Program
{
//0---1---2---3
// |
// 4
// |
// 5---6---7
// \ /
// 8
// |
// 9
static List<List<int>> input1 = new List<List<int>>
{ // 0 1 2 3 4 5 6 7 8 9
new List<int>() {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
new List<int>() {1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
new List<int>() {2, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0},
new List<int>() {3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
new List<int>() {4, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},
new List<int>() {5, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
new List<int>() {6, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0},
new List<int>() {7, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
new List<int>() {8, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1},
new List<int>() {9, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
};
static public void Dijkstra()
{
CGraph cGraph;
cGraph = new CGraph(input1);
Console.WriteLine("-------------Input 1 -------------");
cGraph.PrintGraph();
}
class CGraph
{
List<Node> graph = new List<Node>();
public CGraph(List<List<int>> input)
{
foreach (List<int> inputRow in input)
{
Node newNode = new Node();
newNode.name = inputRow[0];
newNode.distanceDict = new Dictionary<int, Path>();
newNode.visited = false;
newNode.neighbors = new List<Neighbor>();
//for (int index = 1; index < inputRow.Count; index++)
//{
// //skip diagnol values so you don't count a nodes distance to itself.
// //node count start at zero
// // index you have to skip the node name
// //so you have to subtract one from the index
// if ((index - 1) != nodeCount)
// {
// string nodeName = input[index - 1][0];
// int distance = int.P(inputRow[index]);
// newNode.distanceDict.Add(nodeName, new List<string>() { nodeName });
// }
//}
graph.Add(newNode);
}
//initialize neighbors using predefined dictionary
for (int nodeCount = 0; nodeCount < graph.Count; nodeCount++)
{
for (int neighborCount = 0; neighborCount < graph.Count; neighborCount++)
{
//add one to neighbor count to skip Node name in index one
if (input[nodeCount][neighborCount + 1] != 0)
{
Neighbor newNeightbor = new Neighbor();
newNeightbor.node = graph[neighborCount];
newNeightbor.distance = input[nodeCount][neighborCount + 1];
graph[nodeCount].neighbors.Add(newNeightbor);
Path path = new Path();
path.nodeNames = new List<int>() { input[neighborCount][0] };
//add one to neighbor count to skip Node name in index one
path.totalDistance = input[nodeCount][neighborCount + 1];
graph[nodeCount].distanceDict.Add(input[neighborCount][0], path);
}
}
}
foreach (Node node in graph)
{
foreach (Node nodex in graph)
{
node.visited = false;
}
TransverNode(node);
}
}
public class Neighbor
{
public Node node { get; set; }
public int distance { get; set; }
}
public class Path
{
public List<int> nodeNames { get; set; }
public int totalDistance { get; set; }
}
public class Node
{
public int name { get; set; }
public Dictionary<int, Path> distanceDict { get; set; }
public Boolean visited { get; set; }
public List<Neighbor> neighbors { get; set; }
}
static void TransverNode(Node node)
{
if (!node.visited)
{
node.visited = true;
foreach (Neighbor neighbor in node.neighbors)
{
TransverNode(neighbor.node);
int neighborName = neighbor.node.name;
int neighborDistance = neighbor.distance;
//compair neighbors dictionary with current dictionary
//update current dictionary as required
foreach (int key in neighbor.node.distanceDict.Keys)
{
if (key != node.name)
{
int neighborKeyDistance = neighbor.node.distanceDict[key].totalDistance;
if (node.distanceDict.ContainsKey(key))
{
int currentDistance = node.distanceDict[key].totalDistance;
if (neighborKeyDistance + neighborDistance < currentDistance)
{
List<int> nodeList = new List<int>();
nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);
nodeList.Insert(0, neighbor.node.name);
node.distanceDict[key].nodeNames = nodeList;
node.distanceDict[key].totalDistance = neighborKeyDistance + neighborDistance;
}
}
else
{
List<int> nodeList = new List<int>();
nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);
nodeList.Insert(0, neighbor.node.name);
Path path = new Path();
path.nodeNames = nodeList;
path.totalDistance = neighbor.distance + neighborKeyDistance;
node.distanceDict.Add(key, path);
}
}
}
}
}
}
public void PrintGraph()
{
foreach (Node node in graph)
{
Console.WriteLine("Node : {0}", node.name);
foreach (int key in node.distanceDict.Keys.OrderBy(x => x))
{
Console.WriteLine(" Distance to node {0} = {1}, Path : {2}", key, node.distanceDict[key].totalDistance, string.Join(",", node.distanceDict[key].nodeNames.ToArray()));
}
}
}
}
}
}
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（62条）