小编Mei*_*eir的帖子

我试图理解为什么Dijkstra的算法不适用于负权重.阅读最短路径上的示例,我试图找出以下场景:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

来自网站:

假设边缘全部从左向右指向,如果我们从A开始,Dijkstra算法将选择最小化d(A,A)+长度(边缘)的边(A,x),即(A,B).然后设置d(A,B)= 2并选择另一个边(y,C),使d(A,y)+ d(y,C)最小化; 唯一的选择是(A,C),它设置d(A,C)= 3.但它从未找到从A到B的最短路径,通过C,总长度为1.

我无法理解为什么使用Dijkstra的以下实现,d [B]将不会更新为1(当算法到达顶点C时,它将在B上运行放松,看到d [B]等于2,因此更新它的价值1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ? Ø
   Q ? V[G]//priority queue by d[v]
   while Q ? Ø do
      u ? Extract-Min(Q)
      S ? S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v ? V(G)
      d[v] ? ?
      ?[v] …

据我所知,为了检测链表中的循环,我可以使用Hare和Tortoise方法,它有2个指针(慢速和快速).但是,在阅读了wiki和其他资源之后,我不明白为什么保证这两个指针在O(n)时间复杂度上会满足.

我有一个包含类别名称的列表，例如cats = ["tv", "movie", "theater"]。我想编写一个 url 模式来仅捕获包含列表中项目之一的 URL，例如：

url(r'^site/CATEGORY_NAME/$', 'mainsite.views.home'),

这样CATEGORY_NAME就只能列出猫中的一项。我怎样才能做到这一点？

谢谢，梅尔