Dijkstra的算法问题 [英] Dijkstra's Algorithm Issue
问题描述
我正在研究一个程序，该程序必须找到从西雅图到迈阿密的12个城市之间的最短路径。我正在使用Dijkstra的算法，因为路径是加权的。到目前为止，这是我的代码，尽管它是正确的，但除了我得到的答案不是我所需的答案之外，其他所有方法都可以正常工作。
这部分代码设置了所有内容
class Graph
{
Dictionary< string，Dictionary< string ，int>> vertices = new Dictionary< string，Dictionary< string，int>>（）;
public void add_vertex（字符串名称，字典< string，int>边）
{
vertices [name] = edge;
}
公共列表< string> shortest_path（字符串开头，字符串结尾）
{
var previous = new Dictionary< string，string>（）;
var distances = new Dictionary< string，int>（）;
var nodes = new List< string>（）;
List< string> path = null;
foreach（顶点中的可变顶点）
{
if（vertex.Key == start）
{
distances [vertex.Key] = 1 ;
}
else
{
distances [vertex.Key] = int.MaxValue;
}
个节点。Add（vertex.Key）;
}
而（nodes.Count！= 0）
{
nodes.Sort（（x，y）=> distances [x]-distances [ y]）；
var minimum = nodes [0];
个节点。删除（最小）；
如果（最小==完成）
{
path = new List< string>（）;
while（previous.ContainsKey（smallest））
{
path.Add（smallest）;
最小=上一个[最小]；
}
休息时间；
}
如果（距离[最小] == int.MaxValue）
{
休息；
}
foreach（顶点处的var邻居[最小]）
{
var alt =距离[最小] + neighbor.Value;
if（alt< distances [neighbor.Key]）
{
distances [neighbor.Key] = alt;
previous [neighbor.Key] =最小；
}
}
}
返回路径；
}
}
下面是我创建城市的地方
class MainClass
{
public static void Main（string [] args ）
{
图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}，{ 达拉斯，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（波士顿，新的Dictionary< string，int>（）{{芝加哥，1613}，{华盛顿特区，725}，{纽约，338}}）;
g.add_vertex（ New York，new Dictionary< string，int>（）{{华盛顿特区，383}，{波士顿，338}，{迈阿密，2145}}）;
g.add_vertex（ Miami，new Dictionary< string，int>（）{{ Dallas，2161}，{ Washington DC，1709}，{ New York，2145}}）;
g.shortest_path（迈阿密，西雅图）.ForEach（x => Console.Write（x +>））;;
}
}
我需要弄清楚的部分是何时运行程序，我得到：西雅图>丹佛>达拉斯。对于离迈阿密最短的距离，这个答案是正确的，但是我需要到每个城市的最短距离，而不仅仅是迈阿密。我只是不知道需要更改什么才能正确显示它。
据我所知，提供的代码实现了< href = http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm rel = nofollow> Dijkstra的算法，已修改为一旦将某些所需的目标节点选择到节点集中就终止从起始节点开始的最短路径是已知的。 Dijkstra的算法解决了所谓的单源最短路径问题。这意味着指定了一些初始节点，在这种情况下为 Miami ，并且到所有其他节点的最短路径构成了所需的结果。它不能解决全对子最短路径问题，该问题需要计算每对节点各自的距离。但是，可以通过 Floyd-Warshall算法来解决。 / p>
相反，如果您需要从迈阿密到所有其他城市的最短路径，请修改实现不尽早打破循环并删除第二个参数。
I'm working on a program where I have to find the shortest path between 12 cities, starting in Seattle and ending in Miami. I'm using Dijkstra's Algorithm because the paths are weighted. Here is my code so far, it all works except the answer I get is not the one I need, although it is correct.
This part of the code sets everything up as well as creates the sorting algorithm.
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;
}
}
Below is where I create the "cities" along with creating the values between them.
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 + " > "));
}
}
The part that I need help figuring out is when I run the program, I get: Seattle > Denver > Dallas. That answer is correct for the shortest distance to Miami, but I need the shortest distance to every city, not just Miami. I just don't know what I need to change to display that properly.
To my understanding, the provided code implements Dijkstra's Algorithm, modified to terminate as soon as some desired destination node is selected into the set of nodes for which the shortest path from the initial node is known. Dijkstra's algorithm solves the so-called Single Source Shortest Path problem. This means that some initial node, in this case Miami, is specified, and the desired result is consituted by the shortest paths to all other nodes. It does not solve the All-Pairs Shortest Path problem, which requires calculation of the respective distance for each pair nodes. This problem can be solved by the Floyd-Warshall Algorithm, however.
In contrast, if you need the shortest path from Miami to all other cities, modifiy the implementation not to break the loop early and remove the second argument.
这篇关于Dijkstra的算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
