1 文本格式
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public class Node // : IComparable<Node>
{
private int vertex, weight;
public Node(int v, int w)
{
vertex = v;
weight = w;
}
public int getVertex() { return vertex; }
public int getWeight() { return weight; }
public int CompareTo(Node other)
{
return weight - other.weight;
}
}
public class Dijkstra_Algorithm
{
// Function to find the shortest distance of all the
// vertices from the source vertex S.
public static int[] dijkstra(int V, List<List<Node>> graph, int src)
{
int[] distance = new int[V];
for (int i = 0; i < V; i++)
{
distance[i] = Int32.MaxValue;
}
distance[src] = 0;
SortedSet<Node> pq = new SortedSet<Node>();
pq.Add(new Node(src, 0));
while (pq.Count > 0)
{
Node current = pq.First();
pq.Remove(current);
foreach (Node n in graph[current.getVertex()])
{
if (distance[current.getVertex()] + n.getWeight() < distance[n.getVertex()])
{
distance[n.getVertex()] = n.getWeight() + distance[current.getVertex()];
pq.Add(new Node(n.getVertex(), distance[n.getVertex()]));
}
}
}
// If you want to calculate distance from source to
// a particular target, you can return
// distance[target]
return distance;
}
public static string Drive()
{
int V = 9;
List<List<Node>> graph = new List<List<Node>>();
for (int i = 0; i < V; i++)
{
graph.Add(new List<Node>());
}
int source = 0;
graph[0].Add(new Node(1, 4));
graph[0].Add(new Node(7, 8));
graph[1].Add(new Node(2, 8));
graph[1].Add(new Node(7, 11));
graph[1].Add(new Node(0, 7));
graph[2].Add(new Node(1, 8));
graph[2].Add(new Node(3, 7));
graph[2].Add(new Node(8, 2));
graph[2].Add(new Node(5, 4));
graph[3].Add(new Node(2, 7));
graph[3].Add(new Node(4, 9));
graph[3].Add(new Node(5, 14));
graph[4].Add(new Node(3, 9));
graph[4].Add(new Node(5, 10));
graph[5].Add(new Node(4, 10));
graph[5].Add(new Node(6, 2));
graph[6].Add(new Node(5, 2));
graph[6].Add(new Node(7, 1));
graph[6].Add(new Node(8, 6));
graph[7].Add(new Node(0, 8));
graph[7].Add(new Node(1, 11));
graph[7].Add(new Node(6, 1));
graph[7].Add(new Node(8, 7));
graph[8].Add(new Node(2, 2));
graph[8].Add(new Node(6, 6));
graph[8].Add(new Node(7, 1));
int[] distance = dijkstra(V, graph, source);
// Printing the Output
StringBuilder sb = new StringBuilder();
sb.AppendLine("Vertex " + " Distance from Source");
for (int i = 0; i < V; i++)
{
sb.AppendLine(i + "\t" + distance[i]);
}
return sb.ToString();
}
}
}
2 代码格式
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public class Node
{
private int vertex, weight;
public Node(int v, int w)
{
vertex = v;
weight = w;
}
public int getVertex() { return vertex; }
public int getWeight() { return weight; }
public int CompareTo(Node other)
{
return weight - other.weight;
}
}
public class Dijkstra_Algorithm
{
// Function to find the shortest distance of all the
// vertices from the source vertex S.
public static int[] dijkstra(int V, List<List<Node>> graph, int src)
{
int[] distance = new int[V];
for (int i = 0; i < V; i++)
{
distance[i] = Int32.MaxValue;
}
distance[src] = 0;
SortedSet<Node> pq = new SortedSet<Node>();
pq.Add(new Node(src, 0));
while (pq.Count > 0)
{
Node current = pq.First();
pq.Remove(current);
foreach (Node n in graph[current.getVertex()])
{
if (distance[current.getVertex()] + n.getWeight() < distance[n.getVertex()])
{
distance[n.getVertex()] = n.getWeight() + distance[current.getVertex()];
pq.Add(new Node(n.getVertex(), distance[n.getVertex()]));
}
}
}
// If you want to calculate distance from source to
// a particular target, you can return
// distance[target]
return distance;
}
public static string Drive()
{
int V = 9;
List<List<Node>> graph = new List<List<Node>>();
for (int i = 0; i < V; i++)
{
graph.Add(new List<Node>());
}
int source = 0;
graph[0].Add(new Node(1, 4));
graph[0].Add(new Node(7, 8));
graph[1].Add(new Node(2, 8));
graph[1].Add(new Node(7, 11));
graph[1].Add(new Node(0, 7));
graph[2].Add(new Node(1, 8));
graph[2].Add(new Node(3, 7));
graph[2].Add(new Node(8, 2));
graph[2].Add(new Node(5, 4));
graph[3].Add(new Node(2, 7));
graph[3].Add(new Node(4, 9));
graph[3].Add(new Node(5, 14));
graph[4].Add(new Node(3, 9));
graph[4].Add(new Node(5, 10));
graph[5].Add(new Node(4, 10));
graph[5].Add(new Node(6, 2));
graph[6].Add(new Node(5, 2));
graph[6].Add(new Node(7, 1));
graph[6].Add(new Node(8, 6));
graph[7].Add(new Node(0, 8));
graph[7].Add(new Node(1, 11));
graph[7].Add(new Node(6, 1));
graph[7].Add(new Node(8, 7));
graph[8].Add(new Node(2, 2));
graph[8].Add(new Node(6, 6));
graph[8].Add(new Node(7, 1));
int[] distance = dijkstra(V, graph, source);
// Printing the Output
StringBuilder sb = new StringBuilder();
sb.AppendLine("Vertex " + " Distance from Source");
for (int i = 0; i < V; i++)
{
sb.AppendLine(i + "\t" + distance[i]);
}
return sb.ToString();
}
}
}
