Ứng dụng thuật toán Dijkstra trong Shortest Path Routing để tìm đường đi ngắn nhất

ợc định nghĩa : a=[v,v] hoặc a=[i,k]. k được gọi là cận kề hướng ra đối với i nếu một cung [i,k] tồn tại và bậc hướng ra của i là số lượng các cung như vậy. Một graph goi là một mạng nếu các liên kết và các nút có mặt trong liên kết có các thuộc tính (chẳng hạn như độ dài, dung lượng, loại,…). Các mạng được sử dụng để mô hình các vấn đề cần quan tâm trong truyền thông, các thuộc tính riêng biệt của các nút và liên kết thì liên quan đến các vấn đề cụ thể trong truyền thông. Một graph có các liên kết gọi là graph vô hướng, tuy nhiên một graph vô hướng, tuy nhiên một graph có các cung gọi là graph hữu hướng. Một graph hữu hướng có thể có cả các liên kết vô hướng. Thông thường, các graph được giả sử là vô hướng, hoặc sự phân biệt đó là không có ý nghĩa. Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kết giữa cùng một cặp nút. Những liên kết như vậy gọi là các liên kết song song. Một graph có liên kết song song gọi là một multigraph. Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nút đó. Những liên kết đó được gọi là các self loop. Một graph không có các liên kết song song hoặc các self loop gọi là một graph đơn giản. Lý thuyết nghiên cứu Định tuyến đường dẫn ngắn nhất (Shortest Path Routing): Bài toán tìm đường đi ngắn nhất là một bài toán khá quan trọng trong quá trình thiết kế và phân tích mạng. Hầu hết các bài toán định tuyến có thể giải quyết như giải quyết bài toán tìm đường đi ngắn nhất khi một “độ dài” thích hợp được gắn vào mỗi cạnh (hoặc cung) trong mạng. Trong khi các thuật toán thiết kế thì cố gắng tìm kiếm cách tạo ra các mạng thỏa mãn tiêu chẩn độ dài đường đi. Bài toán đơn giản nhất của loại toán này là tìm đường đi ngắn nhất giữa hai nút cho trước. Loại bài toán này có thể là bài toán tìm đường đi ngắn nhất từ một nút tới tất cả các nút còn lại, tương đương bài toán tìm đường đi ngắn nhất từ tất cả các điểm đến một điểm. Đôi khi đòi hỏi phải tìm đường đi ngắn nhất giữa tất cả các cặp nút. Ta xét các graph hữu hướng và giả sử rằng đã biết độ dài của một cung giữa mỗi cặp nút i và j là l. Các độ dài này không cần phải đối xứng. Khi một cung không tồn tại thì độ dài l được giả sử là rất lớn (chẳng hạn lớn gấp n lần độ dài cung lớn nhất trong mạng). Chú ý rằng có thể áp dụng quá trình này cho các mạng vô hướng bằng cách thay mỗi cạnh bằng hai cung có cùng độ dài. Ban đầu giả sử rằng l là dương hoàn toàn; sau đó giả thiết này có thể được thay đổi. Phần lớn các mạng chuyển mạch gói sử dụng các thuật toán khác nhau của phương pháp chọn tuyến đường ngắn nhất do lớp mạng thực hiện. Một số mạng chọn tuyến theo cách thức tập trung, thiết lập đường dẫn giữa nút nguồn và nút đích ở trung tâm điều hành mạng NMC (Network Management Center) hay trung tâm điều khiển chọn tuyến RCC (Routing Control Center) rồi sau đó phân phối các thông tin chọn tuyến đến tất cả các nút chuyển mạch trong mạng. Các nút mạng khác sử dụng cách thức phi tập trung hay còn gọi là cách thức phân bố, từng nút trao đổi thông tin chọn tuyến và giá thành với các nút khác trong mạng trên cơ sở tương tác cho đến khi các bảng định tuyến đáp ứng được yêu cầu định tuyến ngắn nhất. Thuật toán Dijkstra: Tất cả các thuật toán tìm đường đi ngắn nhất đều dựa vào việc lồng nhau giữa các đường đi ngắn nhất nghĩa là một nút k thuộc một đường đi ngắn nhất từ i tới j thì đường đi ngắn nhất từ i tới j sẽ bằng đường đi ngắn nhất từ i tới k kết hợp với đường đi ngắn nhất từ j tới k. Vì thế chúng ta có thể tìm đường đi ngắn nhất bằng công thức đệ quy sau: d = (d + d) Hình 2. Các đường đi ngắn nhất lồng nhau. Dxy là độ dài của đường đi ngắn nhất từ x tới y. Khó khăn của cách tiếp cận này là phải có một cách khởi động đệ quy nào đó vì chúng ta không thể khởi động với các giá trị bất kỳ ở vế phải của phương trình trên. Thuật toán Dijkstra phù hợp cho việc tìm đường đi ngắn nhất từ một nút i tới tất cả các nút khác. Bắt đầu bằng cách thiết lập d = 0 và d = ¥ " i ≠ j Sau đó thiết lập d ¬ l " j là nút kề cận của i Sau đó tìm nút j có d là bé nhất. Tiếp đó lấy chính nút j vừa chọn để khai triển các khoảng cách các nút khác, nghĩa là bằng cách thiết lập d ¬ min(d, d + l) Tại mỗi giai đoạn của quá trình, giá trị của d là giá trị ước lượng hiện có của đường đi ngắn nhất từ i tới k, và thực ra là độ dài đường đi ngắn nhất đã được tìm cho tới thời điểm đó. Xem d như là nhãn trên nút k. Quá trình sử dụng một nút để triển khai các nhãn cho các nút khác gọi là quá trình quét nút. Thực hiện tương tự, tiếp tục tìm các nút chưa được quét có nhãn bé nhất và quét nó. Chú ý rằng, vì giả thiết tất cả các l đều dương do đó một nút không thể gán cho nút khác một nhãn bé hơn chính nhãn của nút đó. Vì vậy, khi một nút được quét thì việc quét lại nó nhất thiết không bao giờ xảy ra. Nếu nhãn trên một nút thay đổi, nút đó phải được quét lại. Ví dụ : xét mạng như hình sau, trên mỗi đường ghép nối có các trọng số tương ứng với giá thành của từng đường, để đơn giản ta coi các trọng số này theo cả hai chiều là như nhau, mặc dù trên thực tế chúng có thể khác nhau về giá trị. Để chọn được đường dẫn ngắn nhất từ một nguồn tới tất cả các nút trong mạng, đòi hỏi phải có kiến thức về cấu hình tổng thể của mạng (danh sách các nút và các ghép nối giữa chúng) cũng như giá thành của từng đường nối. Điều đó dẫn tới việc tính toán tập trung dựa trên thông tin đầy đủ lưu trong các cơ sở dữ liệu trung tâm (Central Database). Hình 3. Ví dụ một mạng. Thuật toán được thực hiện theo từng bước, xây dựng mô hình cây đường ngắn nhất (Shortest Path Tree) có gốc tại nút nguồn (nút 1). Các đường dẫn ngắn nhất tới k nút khác được tính toán trong k bước, chúng được tập hợp lại trong tập N. Coi D(v) là khoảng cách (tổng của các trọng số đường nối dọc theo đường dẫn) từ nút nguồn 1 tới nút v. Coi l(i,j) là giá thành đã cho giữa 2 nút i và j. Thuật toán gồm 2 bước: 1.Bước khởi đầu Đặt N={1} (tập N ban đầu chỉ gồm duy nhất 1 nút), với mỗi nút v Ï N đặt D(v)=l(l,v), với các nút không nối trực tiếp với nút l ta coi giá thành bằng ¥ . 2.Bước lặp Tìm nút w không thuộc N sao cho D(w) là tối thiểu và bổ sung w vào tập N. Sau đó thay D(v) cho toàn bộ các nút không thuộc N còn lại bằng cách tính: D(v) ¬ min[D(v),D(w) + l(w,v)] Bước này được lặp lại cho đến khi tất cả các nút đều có trong N. Sau khi thực hiện, ta lần lượt có được các bước mô tả bởi bảng thống kê sau: Bước Tập N D(2) D(3) D(4) D(5) D(6) 0 {1} 2 ¥ ¥ ¥ 5 1 {1,2} 2 3 ¥ ¥ 3 2 {1,2,3} 2 3 4 5 3 3 {1,2,3,6} 2 3 4 5 3 4 {1,2,3,6,4} 2 3 4 5 3 5 {1,2,3,6,4,5} 2 3 4 5 3 Mô hình cây đường đi ngắn nhất nếu lấy nút 1 làm nút nguồn có thể mô tả như hình vẽ sau: Hình 4.Mô hình đường dẫn ngắn nhất. Đích Nút tiếp theo 2 2 3 3 4 4 5 5 6 3 Hình 5.Bảng chọn tuyến cho nút 1. Với thuật toán này ta có thể tính được các tuyến đường có đường dẫn ngắn nhất cho từng nút, cụ thể ta coi nút đó là nút nguồn rồi thực hiện các bước giải thuật kể trên. Trong trường hợp chọn tuyến theo phương thức tập trung, NMC sẽ gửi các bảng chọn tuyến cho từng nút một sau khi đã thiết lập xong, còn nếu mạng sử dụng phương thức phân bố thì từng nút phải tính lấy bảng định tuyến, cùng sử dụng các thông tin tổng thể như trên (được cung cấp bởi các nút lân cận hoặc bởi NMC) và chọn ra cây đường dẫn cho riêng nó. Xây dựng và thiết kế chương trình minh họa thuật toán Dijkstra Xây dựng chương trình cơ bản tìm đường đi ngắn nhất bằng thuật toán Dijkstra: Viết bằng ngôn nữa C: #include #include #include #define filein “Dijkstra.inp” #define fileout “Dijkstra.out” #define NMAX 100 #define MAX 1000 int n,s,t; int c[NMAX][NMAX]; int Previous[NMAX]; bool Free[NMAX]; int d[NMAX]; void Input_data(){ int i,j; FILE *fp; fp=fopen(filein,”r”); fscanf(fp,”%d%d%d”,&n,&s,&t); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ fscanf(fp,”%d”,&c[i][j]); if(c[i][j]==0) c[i][j]=MAX; } } fclose(fp); } void Init(){ int v; for(v=1;v<=n;v++){ d[v]=c[s][v]; //Khởi tạo giá trị đầu minpath từ s đến v là v=c[s][v] //Đánh dấu Previous[v]=s; //Tất cả các đỉnh đều ở trạng thái tự do Free[v]=true; } //cố định s Previous[s]=0; d[s]=0; Free[s]=false; } void Dijkstra(){ int u,v,minp; //thực hiện trong khi t còn tự do While(Free[t]){ minp=MAX; //Tìm trong tập T ra đỉnh u có d[u] min. Chú ý T là tập hợp các đỉnh chưa //có đính nhãn for(v=1;v<=n;v++){ if(Free[v]&&(minp>d[v])){ minp=d[v]; u=v; } } //Sau khi tìm được đỉnh u thì ta cố định đỉnh u Free[u]=false; //Dùng đỉnh u để tối ưu hóa các đỉnh trong T if(Free[t]){ for( v=1;v<=n;v++){ if(Free[v]&&(d[u]+c[u][v]<d[v])){ //Sửa lại nhãn của v d[v]=d[u]+c[u][v]; //Lưu vết Previous[v]=u; } } } } } Void Output_data(){ Int i; FILE *fp; fp=fopen(fileout,”w”); fprintf(fp,”+Duong di ngan nhat tu %d den %d la: \n”,s,t); fprintf(fp,”%d<=”,t); i=Previous[t]; while(i!=s){ fprintf(fp,”%d<=”,i); i=Previous[i]; } fprintf(fp,”%d”,s); fprintf(fp,”\n+Do dai duong di ngan nhat la: %d”,d[t]); fclose(fp); } Thiết kế phần mềm minh họa thuật toán Dijkstra: Sử dụng bộ công cụ Eclipse lập trình với Java. Class Options: Class Options chứa các Button để thực hiện việc vẽ các đỉnh, các cạnh (chi phí), sửa, xóa, chạy thực thi thuật toán Dijkstra. package Dijkstra3; import java.awt.Button; import java.awt.Event; import java.awt.GridLayout; import java.awt.Panel; class Options extends Panel { /** * */ private static final long serialVersionUID = 1L; // Dat cac Options ben trai man hinh ung dung Button b1 = new Button("Clear"); Button b2 = new Button("Run"); Button b3 = new Button("Step"); Button b4 = new Button("Reset"); Button b5 = new Button("Example"); Button b6 = new Button("Exit"); Button b7 = new Button("About"); GraphAlgorithm parent; boolean Locked=false; Options(GraphAlgorithm myparent) { parent = myparent; setLayout(new GridLayout(7, 1, 0, 10)); add(b1); add(b2); add(b3); add(b4); add(b5); add(b7); add(b6); } public boolean action(Event evt, Object arg) { if (evt.target instanceof Button) { //Neu la JButton "Step" va Unlock thi thuc hien buoc dau tien va hien thi "Nextstep" len JButton, //nguoc lai thi khong thuc hien if (((String)arg).equals("Step")) { if (!Locked) { b3.setLabel("Next step"); parent.graphcanvas.stepalg(); } else parent.documentation.doctext.showline("locked"); } //Neu la JButton "Nextstep" thi thuc hien buoc tiep thep if (((String)arg).equals("Next step")){ parent.graphcanvas.nextstep(); } //Neu la JButton "Reset" thi thuc hien reset if (((String)arg).equals("Reset")) { parent.graphcanvas.reset(); b3.setLabel("Step"); parent.documentation.doctext.showline("all items"); } //Neu la JButton "Clear" thi xoa graphics if (((String)arg).equals("Clear")) { parent.graphcanvas.clear(); b3.setLabel("Step"); parent.documentation.doctext.showline("all items"); } //Neu la JButton "Run" va Unlock thi thuc hien tung buoc mac dinh //nguoc lai thi khong thuc hien if (((String)arg).equals("Run")) { if (!Locked) parent.graphcanvas.runalg(); else parent.documentation.doctext.showline("locked"); } //Neu la JButton "Example" va Unlock thi thuc hien default graphics //nguoc lai thi khong thuc hien if (((String)arg).equals("Example")) { if (!Locked) parent.graphcanvas.showexample(); else parent.documentation.doctext.showline("locked"); } //Neu la JButton "About" thi hien thi dialog About if(((String)arg).equals("About")){ dialog dig = new dialog(); } //Neu la JButton "Exit" thi thoat khoi chuong trinh if (((String)arg).equals("Exit")) { System.exit(0); } } return true; } public void lock() { Locked=true; } public void unlock() { Locked=false; b3.setLabel("Step"); } } Class Documentation: Class Documentation chứa document hướng dẫn sử dụng chương trình và các chỉ dẫn cùng với việc minh họa chi phí giữa các đỉnh trong quá trình chạy thực hiện giải thuật Dijkstra. package Dijkstra3; import java.awt.BorderLayout; import java.awt.Choice; import java.awt.Event; import java.awt.GridLayout; import java.awt.Label; import java.awt.Panel; import java.awt.TextArea; class Documentation extends Panel { // Documentaion huong dan o phia tren man hinh ung dung DocOptions docopt = new DocOptions(this); DocText doctext = new DocText(); Documentation() { setLayout(new BorderLayout(10, 10)); add("West", docopt); add("Center", doctext); } } class DocOptions extends Panel { //Tao Choice huong dan ben trai man hinh ung dung Choice doc = new Choice(); Documentation parent; DocOptions(Documentation myparent) { setLayout(new GridLayout(2, 1, 5, 0)); parent = myparent; add(new Label("DOCUMENTATION:")); doc.addItem("draw nodes"); doc.addItem("remove nodes"); doc.addItem("move nodes"); doc.addItem("the startnode"); doc.addItem("draw arrows"); doc.addItem("change weights"); doc.addItem("remove arrows"); doc.addItem("clear / reset"); doc.addItem("run algorithm"); doc.addItem("step through"); doc.addItem("example"); doc.addItem("about"); doc.addItem("exit"); doc.addItem("all items"); add(doc); } public boolean action(Event evt, Object arg) { //Ham xu ly Choice if (evt.target instanceof Choice) { String str=new String(doc.getSelectedItem()); parent.doctext.showline(str); } return true; } } class DocText extends TextArea { //TextDocumentation huong dan cho cac Choice va JButton final String drawnodes = new String("DRAWING NODES:\n"+ "Draw a node by clicking the mouse on the screen application.\n\n"); final String rmvnodes = new String("REMOVE NODES:\n"+ "To remove a node press and click on the node.\n"+ "You can not remove the startnode.\n"+ "Select another startnode, then you can remove the node.\n\n"); final String mvnodes = new String("MOVING NODES\n"+ "To move a node press , click on the node,\nand drag it to"+ " its new position.\n\n"); final String startnode = new String("STARTNODE:\n"+ "The startnode is blue, other nodes are grey.\n"+ "The first node you draw on the screen will be the startnode.\n"+ "To select another startnode press , click on the startnode,\n"+ "and drag the mouse to another node.\n"+ "To delete the startnode, first select another startnode, and then"+ "\nremove the node the usual way.\n\n"); final String drawarrows = new String("DRAWING ARROWS:\n"+ "To draw an arrow click mouse in a node,"+ "and drag it to another node.\n\n"); final String weight = new String("CHANGING WEIGHTS:\n"+ "To change the weight of an arrow, click on the arrowhead and drag\n"+ "it along the arrow.\n\n"); final String rmvarrows = new String("REMOVE ARROWS:\n"+ "To remove an arrow, change its weight to 0.\n\n"); final String clrreset = new String(" BUTTON: "+ "Remove the current graph from the screen.\n"+ " BUTTON: "+ "Remove the results of the algorithm from the graph,\n"+ " and unlock screen.\n\n"); final String runalg = new String(" BUTTON: "+ "Run the algorithm on the graph, there will be a time\n" + "delay of +/- 1 second between steps.\n"+ "To run the algorithm slower, use .\n"); final String step = new String(" BUTTON: " + "An opportunity to step through the algorithm.\n"); final String example = new String(" BUTTON: "+ "Displays a default graph on the screen for you.\n"+ "You can then use or \n"); final String exitbutton = new String(" BUTTON: " + "Only works if applet is run with appletviewer.\n"); final String aboutbutton = new String(" BUTTON: " + "Show about Dijkstra program information.\n"); final String toclose = new String("ERROR: "+ "This position is to close to another node/arrow.\n"); final String done = new String("Algorithm has finished, " + "follow green arrows from startnode to any node "+ "to get\nthe shortest path to " + "the node. The length of the path is written in the node.\n" + "press to reset the graph, and unlock the screen."); final String some = new String("Algorithm has finished, " + "follow green arrows from startnode to any node "+ "to get\nthe shortest path to " + "the node. The length of the path is written in the node.\n" + "There are no paths from the startnode to any gray node.\n" + "press to reset the graph, and unlock the screen."); final String none = new String("Algorithm has finished, " + "there are no nodes reachable from the start node.\n"+ "press to reset the graph, and unlock the screen."); final String maxnodes = new String("ERROR: "+ "Maximum number of nodes reached!\n\n"); final String info = new String("DOCUMENTATION:\n"+ "You can scroll through the documentation or get documentation\n"+ "on a specific "+ "item by selecting the item on the left.\nSelecting "+ "brings you back "+ " to the scrolling text.\n\n"); final String locked = new String("ERROR: "+ "Keyboard/mouse locked for this action.\n"+ "Either press or .\n"); final String doc = info + drawnodes + rmvnodes + mvnodes + startnode + drawarrows + weight + rmvarrows + clrreset + runalg + step + example + aboutbutton + exitbutton; DocText() { super(5, 2); setEditable(false); setText(doc); } public void showline(String str) { if (str.equals("draw nodes")) setText(drawnodes); else if (str.equals("remove nodes")) setText(rmvnodes); else if (str.equals("move nodes")) setText(mvnodes); else if (str.equals("the startnode")) setText(startnode); else if (str.equals("draw arrows")) setText(drawarrows); else if (str.equals("change weights")) setText(weight); else if (str.equals("remove arrows")) setText(rmvarrows); else if (str.equals("clear / reset")) setText(clrreset); else if (str.equals("run algorithm")) setText(runalg); else if (str.equals("step through")) setText(step); else if (str.equals("example")) setText(example); else if (str.equals("exit")) setText(exitbutton); else if (str.equals("about")) setText(aboutbutton); else if (str.equals("all items")) setText(doc); else if (str.equals("toclose")) setText(toclose); else if (str.equals("done")) setText(done); else if (str.equals("locked")) setText(locked); else if (str.equals("maxnodes")) setText(maxnodes); else if (str.equals("none")) setText(none); else if (str.equals("some")) setText(some); else setText(str); } } Class dialog: Class dialog chưa thông tin về phần mềm, người viết. package Dijkstra3; import java.awt.*; import java.awt.Component; import java.awt.GridBagConstraints; import java.awt.GridBagLayout; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.ImageIcon; import javax.swing.JButton; import javax.swing.JDialog; import javax.swing.JLabel; import javax.swing.JPanel; class dialog extends JDialog implements ActionListener{ //tao Button OK JButton jb=new JButton("OK"); //tao JPanel JPanel jp1=new JPanel(); JPanel jp2=new JPanel(new GridLayout(3,1)); JPanel jp3=new JPanel(); ImageIcon img=new ImageIcon(this.getClass().getResource("/nhanntv/nhanntv1.png")); //tao JLabel JLabel jlb1=new JLabel(img); JLabel jlb2=new JLabel("************Program Java to************"); JLabel jlb3=new JLabel("****Dijkstra Algorithm Program Demo****"); JLabel jlb4=new JLabel("***CopyWrite @2011 Edit by Nhanntv***"); //Tao Layout GridBagLayout gb=new GridBagLayout(); GridBagConstraints gbc=new GridBagConstraints(); private static final long serialVersionUID = 1L; public dialog(){ setSize(300,200); setLayout(gb); jp1.add(jlb1); jp2.add(jlb2); jp2.add(jlb3); jp2.add(jlb4); jb.addActionListener(this); jp3.add(jb); gbc.fill=GridBagConstraints.EAST; addComponent(jp1,0,0,4,10); gbc.fill=GridBagConstraints.NORTHWEST; addComponent(jp2,0,10,3,15); gbc.fill=GridBagConstraints.NORTHWEST; addComponent(jp3,3,15,1,5); this.setVisible(true); } @Override public void actionPerformed(ActionEvent e) { // TODO Auto-generated method stub if(e.getSource()==jb){ this.dispose(); } } public void addComponent(Component c,int row,int col,int nrow,int ncol){ gbc.gridy=row;// toa do y gbc.gridx=col;// toa do x gbc.gridheight=nrow;// so dong chiem gbc.gridwidth=ncol;// so cot chiem gb.setConstraints(c,gbc); add(c); } } Class GraphCanvas: Class GraphCanvas là Class đồ họa của chương trình, chứa các thuật toán giải quyết việc tìm đường đi ngắn nhất trong mạng (Shortest Path Routing), các phương thức để vẽ một mạng, xây dựng và tìm đường, đưa ra kết quả dưới dạng đồ họa cho giải thuật Dijkstra. package Dijkstra3; import java.awt.Canvas; import java.awt.Color; import java.awt.Dimension; import java.awt.Event; import java.awt.Font; import java.awt.FontMetrics; import java.awt.Graphics; import java.awt.Image; import java.awt.Point; class GraphCanvas extends Canvas implements Runnable { // drawing area for the graph final int MAXNODES = 20; final int MAX = MAXNODES+1; final int NODESIZE = 26; final int NODERADIX = 13; final int DIJKSTRA = 1; // basic graph information Point node[] = new Point[MAX]; // node int weight[][] = new int[MAX][MAX]; // weight of arrow Point arrow[][] = new Point[MAX][MAX]; // current position of arrowhead Point startp[][] = new Point[MAX][MAX]; // start and Point endp[][] = new Point[MAX][MAX]; // endpoint of arrow float dir_x[][] = new float[MAX][MAX]; // direction of arrow float dir_y[][] = new float[MAX][MAX]; // direction of arrow // graph information while running algorithm boolean algedge[][] = new boolean[MAX][MAX]; int dist[] = new int[MAX]; int finaldist[] = new int[MAX]; Color colornode[] = new Color[MAX]; boolean changed[] = new boolean[MAX]; // indicates distance change during algorithm int numchanged =0; int neighbours=0; int step=0; // information used by the algorithm to find the next // node with minimum distance int mindist, minnode, minstart, minend; int numnodes=0; // number of nodes int emptyspots=0; // empty spots in array node[] (due to node deletion) int startgraph=0; // start of graph int hitnode; // mouse clicked on or close to this node int node1, node2; // numbers of nodes involved in current action Point thispoint=new Point(0,0); // current mouseposition Point oldpoint=new Point(0, 0); // previous position of node being moved // current action boolean newarrow = false; boolean movearrow = false; boolean movestart = false; boolean deletenode = false; boolean movenode = false; boolean performalg = false; boolean clicked = false; // fonts Font roman= new Font("TimesRoman", Font.BOLD, 12); Font helvetica= new Font("Helvetica", Font.BOLD, 15); FontMetrics fmetrics = getFontMetrics(roman); int h = (int)fmetrics.getHeight()/3; // for double buffering private Image offScreenImage; private Graphics offScreenGraphics; private Dimension offScreenSize; // for run option Thread algrthm; // current algorithm, (in case more algorithms are added) int algorithm; // algorithm information to be displayed in documetation panel String showstring = new String(""); boolean stepthrough=false; // locking the screen while running the algorithm boolean Locked = false; GraphAlgorithm parent; GraphCanvas(GraphAlgorithm myparent) { parent = myparent; init(); algorithm=DIJKSTRA; setBackground(Color.white); } public void lock() { // lock screen while running an algorithm Locked=true; } public void unlock() { Locked=false; } public void start() { if (algrthm != null) algrthm.resume(); } public void init() { for (int i=0;i<MAXNODES;i++) { colornode[i]=Color.gray; for (int j=0; j<MAXNODES;j++) algedge[i][j]=false; } colornode[startgraph]=Color.blue; performalg = false; } public void clear() { // removes graph from screen startgraph=0; numnodes=0; emptyspots=0; init(); for(int i=0; i<MAXNODES; i++) { node[i]=new Point(0, 0); for (int j=0; j<MAXNODES;j++) weight[i][j]=0; } if (algrthm != null) algrthm.stop(); parent.unlock(); repaint(); } public void reset() { // resets a graph after running an algorithm init(); if (algrthm != null) algrthm.stop(); parent.unlock(); repaint(); } public void runalg() { // gives an animation of the algorithm parent.lock(); initalg(); performalg = true; algrthm = new Thread(this); algrthm.start(); } public void stepalg() { // lets you step through the algorithm parent.lock(); initalg(); performalg = true; nextstep(); } public void initalg() { init(); for(int i=0; i<MAXNODES; i++) { dist[i]=-1; finaldist[i]=-1; for (int j=0; j<MAXNODES;j++) algedge[i][j]=false; } dist[startgraph]=0; finaldist[startgraph]=0; step=0; } public void nextstep() { // calculates a step in the algorithm (finds a shortest // path to a next node). finaldist[minend]=mindist; algedge[minstart][minend]=true; colornode[minend]=Color.green; // build more information to display on documentation panel step++; repaint(); } public void stop() { if (algrthm != null) algrthm.suspend(); } public void run() { for(int i=0; i<(numnodes-emptyspots); i++){ nextstep(); try { algrthm.sleep(1000); } catch (InterruptedException e) {} } algrthm = null; } public void showexample() { // draws a default graph on the screen int w, h; clear(); init(); numnodes=6; emptyspots=0; for(int i=0; i<MAXNODES; i++) { node[i]=new Point(0, 0); for (int j=0; j<MAXNODES;j++) weight[i][j]=0; } w=this.size().width/8; h=this.size().height/8; node[0]=new Point(2*w, 4*h); node[1]=new Point(3*w, 2*h); node[2]=new Point(5*w, 2*h); node[3]=new Point(6*w, 4*h); node[4]=new Point(5*w, 6*h); node[5]=new Point(3*w, 6*h); weight[0][1]=4; weight[1][0]=4; weight[0][5]=2; weight[5][0]=2; weight[1][2]=3; weight[2][1]=3; weight[1][4]=3; weight[4][1]=3; weight[2][3]=2; weight[3][2]=2; weight[3][4]=1; weight[4][3]=1; weight[4][5]=3; weight[5][4]=3; for (int i=0;i<numnodes;i++) for (int j=0;j<numnodes;j++) if (weight[i][j]>0) arrowupdate(i, j, weight[i][j]); repaint(); } public boolean mouseDown(Event evt, int x, int y) { if (Locked) parent.documentation.doctext.showline("locked"); else { clicked = true; if (evt.shiftDown()) { // move a node if (nodehit(x, y, NODESIZE)) { oldpoint = node[hitnode]; node1 = hitnode; movenode=true; } } else if (evt.controlDown()) { // delete a node if (nodehit(x, y, NODESIZE)) { node1 = hitnode; if (startgraph==node1) { movestart=true; thispoint = new Point(x,y); colornode[startgraph]=Color.gray; } else deletenode= true; } } else if (arrowhit(x, y, 5)) { // change weihgt of an edge movearrow = true; repaint(); } else if (nodehit(x, y, NODESIZE)) { // draw a new arrow if (!newarrow) { newarrow = true; thispoint = new Point(x, y); node1 = hitnode; } } else if ( !nodehit(x, y, 50) && !arrowhit(x, y, 50) ) { // draw new node if (emptyspots==0) { // take the next available spot in the array if (numnodes < MAXNODES) node[numnodes++]=new Point(x, y); else parent.documentation.doctext.showline("maxnodes"); } else { // take an empty spot in the array (from previously deleted node) int i; for (i=0;i<numnodes;i++) if (node[i].x==-100) break; node[i]=new Point(x, y); emptyspots--; } } else // mouseclick to close to a point or arrowhead, so probably an error parent.documentation.doctext.showline("toclose"); repaint(); } return true; } public boolean mouseDrag(Event evt, int x, int y) { if ( (!Locked) && clicked ) { if (movenode) { // move node and adjust arrows coming into/outof the node node[node1]=new Point(x, y); for (int i=0;i<numnodes;i++) { if (weight[i][node1]>0) { arrowupdate(i, node1, weight[i][node1]); } if (weight[node1][i]>0) { arrowupdate(node1, i, weight[node1][i]); } } repaint(); } else if (movestart || newarrow) { thispoint = new Point(x, y); repaint(); } else if (movearrow) { changeweight(x, y); repaint(); } } return true; } public boolean mouseUp(Event evt, int x, int y) { if ( (!Locked) && clicked ) { if (movenode) { // move the node if the new position is not to close to // another node or outside of the panel node[node1]=new Point(0, 0); if ( nodehit(x, y, 50) || (xthis.size().width) || (ythis.size().height) ) { node[node1]=oldpoint; parent.documentation.doctext.showline("toclose"); } else node[node1]=new Point(x, y); for (int i=0;i<numnodes;i++) { if (weight[i][node1]>0) arrowupdate(i, node1, weight[i][node1]); if (weight[node1][i]>0) arrowupdate(node1, i, weight[node1][i]); } movenode=false; } else if (deletenode) { nodedelete(); deletenode=false; } else if (newarrow) { newarrow = false; if (nodehit(x, y, NODESIZE)) { node2=hitnode; if (node1!=node2) { arrowupdate(node1, node2, 50); if (weight[node2][node1]>0) { arrowupdate(node2, node1, weight[node2][node1]); } parent.documentation.doctext.showline("change weights"); } else System.out.println("zelfde"); } } else if (movearrow) { movearrow = false; if (weight[node1][node2]>0) changeweight(x, y); } else if (movestart) { // if new position is a node, this node becomes the startnode if (nodehit(x, y, NODESIZE)) startgraph=hitnode; colornode[startgraph]=Color.blue; movestart=false; } repaint(); } return true; } public boolean nodehit(int x, int y, int dist) { // checks if you hit a node with your mouseclick for (int i=0; i<numnodes; i++) if ( (x-node[i].x)*(x-node[i].x) + (y-node[i].y)*(y-node[i].y) < dist*dist ) { hitnode = i; return true; } return false; } public boolean arrowhit(int x, int y, int dist) { // checks if you hit an arrow with your mouseclick for (int i=0; i<numnodes; i++) for (int j=0; j<numnodes; j++) { if ( ( weight[i][j]>0 ) && (Math.pow(x-arrow[i][j].x, 2) + Math.pow(y-arrow[i][j].y, 2) < Math.pow(dist, 2) ) ) { node1 = i; node2 = j; return true; } } return false; } public void nodedelete() { // delete a node and the arrows coming into/outof the node node[node1]=new Point(-100, -100); for (int j=0;j<numnodes;j++) { weight[node1][j]=0; weight[j][node1]=0; } emptyspots++; } public void changeweight(int x, int y) { // changes the weight of an arrow (edge in the graph), when a user drags // the arrowhead over the edge connecting node node1 and node2. // direction of the arrow int diff_x = (int)(20*dir_x[node1][node2]); int diff_y = (int)(20*dir_y[node1][node2]); // depending on the arrow direction, follow the x, or the y // position of the mouse while the arrowhead is being dragged boolean follow_x=false; if (Math.abs(endp[node1][node2].x-startp[node1][node2].x) > Math.abs(endp[node1][node2].y-startp[node1][node2].y) ) { follow_x = true; } // find the new position of the arrowhead, and calculate // the corresponding weight if (follow_x) { int hbound = Math.max(startp[node1][node2].x, endp[node1][node2].x)-Math.abs(diff_x); int lbound = Math.min(startp[node1][node2].x, endp[node1][node2].x)+Math.abs(diff_x); // arrow must stay between the nodes if (x<lbound) { arrow[node1][node2].x=lbound; } else if (x>hbound) { arrow[node1][node2].x=hbound; } else arrow[node1][node2].x=x; arrow[node1][node2].y= (arrow[node1][node2].x-startp[node1][node2].x) * (endp[node1][node2].y-startp[node1][node2].y)/ (endp[node1][node2].x-startp[node1][node2].x) + startp[node1][node2].y; // new weight weight[node1][node2]= Math.abs(arrow[node1][node2].x-startp[node1][node2].x-diff_x)* 100/(hbound-lbound); } // do the same if you follow y else { int hbound = Math.max(startp[node1][node2].y, endp[node1][node2].y)-Math.abs(diff_y); int lbound = Math.min(startp[node1][node2].y, endp[node1][node2].y)+Math.abs(diff_y); if (y<lbound) { arrow[node1][node2].y=lbound; } else if (y>hbound) { arrow[node1][node2].y=hbound; } else arrow[node1][node2].y=y; arrow[node1][node2].x= (arrow[node1][node2].y-startp[node1][node2].y) * (endp[node1][node2].x-startp[node1][node2].x)/ (endp[node1][node2].y-startp[node1][node2].y) + startp[node1][node2].x; weight[node1][node2]= Math.abs(arrow[node1][node2].y-startp[node1][node2].y-diff_y)* 100/(hbound-lbound); } } public void arrowupdate(int p1, int p2, int w) { // make a new arrow from node p1 to p2 with weight w, or change // the weight of the existing arrow to w, calculate the resulting // position of the arrowhead int dx, dy; float l; weight[p1][p2]=w; // direction line between p1 and p2 dx = node[p2].x-node[p1].x; dy = node[p2].y-node[p1].y; // distance between p1 and p2 l = (float)( Math.sqrt((float)(dx*dx + dy*dy))); dir_x[p1][p2]=dx/l; dir_y[p1][p2]=dy/l; // calculate the start and endpoints of the arrow, // adjust startpoints if there also is an arrow from p2 to p1 if (weight[p2][p1]>0) { startp[p1][p2] = new Point((int)(node[p1].x-5*dir_y[p1][p2]), (int)(node[p1].y+5*dir_x[p1][p2])); endp[p1][p2] = new Point((int)(node[p2].x-5*dir_y[p1][p2]), (int)(node[p2].y+5*dir_x[p1][p2])); } else { startp[p1][p2] = new Point(node[p1].x, node[p1].y); endp[p1][p2] = new Point(node[p2].x, node[p2].y); } // range for arrowhead is not all the way to the start/endpoints int diff_x = (int)(Math.abs(20*dir_x[p1][p2])); int diff_y = (int)(Math.abs(20*dir_y[p1][p2])); // calculate new x-position arrowhead if (startp[p1][p2].x>endp[p1][p2].x) { arrow[p1][p2] = new Point(endp[p1][p2].x + diff_x + (Math.abs(endp[p1][p2].x-startp[p1][p2].x) - 2*diff_x )* (100-w)/100 , 0); } else { arrow[p1][p2] = new Point(startp[p1][p2].x + diff_x + (Math.abs(endp[p1][p2].x-startp[p1][p2].x) - 2*diff_x )* w/100, 0); } // calculate new y-position arrowhead if (startp[p1][p2].y>endp[p1][p2].y) { arrow[p1][p2].y=endp[p1][p2].y + diff_y + (Math.abs(endp[p1][p2].y-startp[p1][p2].y) - 2*diff_y )* (100-w)/100; } else { arrow[p1][p2].y=startp[p1][p2].y + diff_y + (Math.abs(endp[p1][p2].y-startp[p1][p2].y) - 2*diff_y )* w/100; } } public String intToString(int i) { char c=(char)((int)'a'+i); return ""+c; } public final synchronized void update(Graphics g) { // prepare new image offscreen Dimension d=size(); if ((offScreenImage == null) || (d.width != offScreenSize.width) || (d.height != offScreenSize.height)) { offScreenImage = createImage(d.width, d.height); offScreenSize = d; offScreenGraphics = offScreenImage.getGraphics(); } offScreenGraphics.setColor(Color.white); offScreenGraphics.fillRect(0, 0, d.width, d.height); paint(offScreenGraphics); g.drawImage(offScreenImage, 0, 0, null); } public void drawarrow(Graphics g, int i, int j) { // draw arrow between node i and node j int x1, x2, x3, y1, y2, y3; // calculate arrowhead x1= (int)(arrow[i][j].x - 3*dir_x[i][j] + 6*dir_y[i][j]); x2= (int)(arrow[i][j].x - 3*dir_x[i][j] - 6*dir_y[i][j]); x3= (int)(arrow[i][j].x + 6*dir_x[i][j]); y1= (int)(arrow[i][j].y - 3*dir_y[i][j] - 6*dir_x[i][j]); y2= (int)(arrow[i][j].y - 3*dir_y[i][j] + 6*dir_x[i][j]); y3= (int)(arrow[i][j].y + 6*dir_y[i][j]); int arrowhead_x[] = { x1, x2, x3, x1 }; int arrowhead_y[] = { y1, y2, y3, y1 }; // if edge already chosen by algorithm change color if (algedge[i][j]) g.setColor(Color.green); // draw arrow g.drawLine(startp[i][j].x, startp[i][j].y, endp[i][j].x, endp[i][j].y); g.fillPolygon(arrowhead_x, arrowhead_y, 4); // write weight of arrow at an appropriate position int dx = (int)(Math.abs(7*dir_y[i][j])); int dy = (int)(Math.abs(7*dir_x[i][j])); String str = new String("" + weight[i][j]); g.setColor(Color.black); if ((startp[i][j].x>endp[i][j].x) && (startp[i][j].y>=endp[i][j].y)) g.drawString( str, arrow[i][j].x + dx, arrow[i][j].y - dy); if ((startp[i][j].x>=endp[i][j].x) && (startp[i][j].y<endp[i][j].y)) g.drawString( str, arrow[i][j].x - fmetrics.stringWidth(str) - dx , arrow[i][j].y - dy); if ((startp[i][j].x<endp[i][j].x) && (startp[i][j].y<=endp[i][j].y)) g.drawString( str, arrow[i][j].x - fmetrics.stringWidth(str) , arrow[i][j].y + fmetrics.getHeight()); if ((startp[i][j].xendp[i][j].y)) g.drawString( str, arrow[i][j].x + dx, arrow[i][j].y + fmetrics.getHeight() ); } public void detailsDijkstra(Graphics g, int i, int j) { // check arrow between node i and node j is amongst the arrows to // choose from during this step of the algorithm // check if node j has the next minimal distance to the startnode if ( (finaldist[i]!=-1) && (finaldist[j]==-1) ) { g.setColor(Color.red); if ( (dist[j]==-1) || (dist[j]>=(dist[i]+weight[i][j])) ) { if ( (dist[i]+weight[i][j])<dist[j] ) { changed[j]=true; numchanged++; } dist[j] = dist[i]+weight[i][j]; colornode[j]=Color.red; if ( (mindist==0) || (dist[j]<mindist) ) { mindist=dist[j]; minstart=i; minend=j; } } } else g.setColor(Color.lightGray); } public void endstepDijkstra(Graphics g) { // displays current and final distances of nodes, sets the final distance // for the node that had minimal distance in this step // explains algorithm on documentation panel for (int i=0; i<numnodes; i++) if ( (node[i].x>0) && (dist[i]!=-1) ) { String str = new String(""+dist[i]); g.drawString(str, node[i].x - (int)fmetrics.stringWidth(str)/2 -1, node[i].y + h); // string to distance to nodes on the documentation panel if (finaldist[i]==-1) { neighbours++; if (neighbours!=1) showstring = showstring + ", "; showstring = showstring + intToString(i) +"=" + dist[i]; } } showstring = showstring + ". "; if ( (step>1) && (numchanged>0) ) { if (numchanged>1) showstring = showstring + "Notice that the distances to "; else showstring = showstring + "Notice that the distance to "; for (int i=0; i<numnodes; i++) if ( changed[i] ) showstring = showstring + intToString(i) +", "; if (numchanged>1) showstring = showstring + "have changed!\n"; else showstring = showstring + "has changed!\n"; } else showstring = showstring + " "; if (neighbours>1) { // if there where more canditates explain why this node is taken showstring = showstring + "Node " + intToString(minend) + " has the minimum distance.\n"; //check if there are other paths to minend. int newpaths=0; for (int i=0; i<numnodes; i++) if ( (node[i].x>0) && (weight[i][minend]>0) && ( finaldist[i] == -1 ) ) newpaths++; if (newpaths>0) showstring = showstring + "Any other path to " + intToString(minend) + " visits another red node, and will be longer than " + mindist + ".\n"; else showstring = showstring + "There are no other arrows coming in to "+ intToString(minend) + ".\n"; } else { boolean morenodes=false; for (int i=0; i<numnodes; i++) if ( ( node[i].x>0 ) && ( finaldist[i] == -1 ) && ( weight[i][minend]>0 ) ) morenodes=true; boolean bridge=false; for (int i=0; i<numnodes; i++) if ( ( node[i].x>0 ) && ( finaldist[i] == -1 ) && ( weight[minend][i]>0 ) ) bridge=true; if ( morenodes && bridge ) showstring = showstring + "Since this node forms a 'bridge' to "+ "the remaining nodes,\nall other paths to this node will be longer.\n"; else if ( morenodes && (!bridge) ) showstring = showstring + "Remaining gray nodes are not reachable.\n"; else showstring = showstring + "There are no other arrows coming in to "+ intToString(minend) + ".\n"; } showstring = showstring + "Node " + intToString(minend) + " will be colored green to indicate " + mindist + " is the length of the shortest path to " + intToString(minend) +"."; parent.documentation.doctext.showline(showstring); } public void detailsalg(Graphics g, int i, int j) { // more algorithms can be added later if (algorithm==DIJKSTRA) detailsDijkstra(g, i, j); } public void endstepalg(Graphics g) { // more algorithms can be added later if (algorithm==DIJKSTRA) endstepDijkstra(g); if ( ( performalg ) && (mindist==0) ) { if (algrthm != null) algrthm.stop(); int nreachable = 0; for (int i=0; i<numnodes; i++) if (finaldist[i] > 0) nreachable++; if (nreachable == 0) parent.documentation.doctext.showline("none"); else if (nreachable< (numnodes-emptyspots-1)) parent.documentation.doctext.showline("some"); else parent.documentation.doctext.showline("done"); } } public void paint(Graphics g) { mindist=0; minnode=MAXNODES; minstart=MAXNODES; minend=MAXNODES; for(int i=0; i<MAXNODES; i++) changed[i]=false; numchanged=0; neighbours=0; g.setFont(roman); g.setColor(Color.black); if (step==1) showstring="Algorithm running: red arrows point to nodes reachable from " + " the startnode.\nThe distance to: "; else showstring="Step " + step + ": Red arrows point to nodes reachable from " + "nodes that already have a final distance." + "\nThe distance to: "; // draw a new arrow upto current mouse position if (newarrow) g.drawLine(node[node1].x, node[node1].y, thispoint.x, thispoint.y); // draw all arrows for (int i=0; i<numnodes; i++) for (int j=0; j<numnodes; j++) if (weight [i][j]>0) { // if algorithm is running then perform next step for this arrow if (performalg) detailsalg(g, i, j); drawarrow(g, i, j); } // if arrowhead has been dragged to 0, draw it anyway, so the user // will have the option to make it positive again if (movearrow && weight[node1][node2]==0) { drawarrow(g, node1, node2); g.drawLine(startp[node1][node2].x, startp[node1][node2].y, endp[node1][node2].x, endp[node1][node2].y); } // draw the nodes for (int i=0; i<numnodes; i++) if (node[i].x>0) { g.setColor(colornode[i]); g.fillOval(node[i].x-NODERADIX, node[i].y-NODERADIX, NODESIZE, NODESIZE); } // reflect the startnode being moved g.setColor(Color.blue); if (movestart) g.fillOval(thispoint.x-NODERADIX, thispoint.y-NODERADIX, NODESIZE, NODESIZE); g.setColor(Color.black); // finish this step of the algorithm if (performalg) endstepalg(g); // draw black circles around nodes, write their names to the screen g.setFont(helvetica); for (int i=0; i<numnodes; i++) if (node[i].x>0) { g.setColor(Color.black); g.drawOval(node[i].x-NODERADIX, node[i].y-NODERADIX, NODESIZE, NODESIZE); g.setColor(Color.blue); g.drawString(intToString(i), node[i].x-14, node[i].y-14); } } } Class GraphAlgorithm: Class GraphAlgorithm là Class main của chương trình, chứa các Class còn lại và là Class chạy thực thi chương trình. package Dijkstra3; import java.awt.*; import javax.swing.*; /** * GraphAlgorithm.java * * @author: Nhanntv * @date: November, 2011 * * Applet for explaining graph algorithms. * It currently only explains Dijkstra's shortest path algorithm, * but it can easily be extended to handle more algorithms. * * Copyright 2011, Nhanntv, all rights reserved */ public class GraphAlgorithm extends java.applet.Applet { GraphCanvas graphcanvas = new GraphCanvas(this); //Graphics Dijkstra Options options = new Options(this); //Option Documentation documentation = new Documentation(); //document instruction //Ham khoi tao public void init() { setSize(700,500); setLayout(new BorderLayout(10, 10)); add("Center", graphcanvas); add("North", documentation); add("East", options); } public void start(){ super.start(); } public Insets insets() { return new Insets(10, 10, 10, 10); } //Ham Lock public void lock() { graphcanvas.lock(); options.lock(); } //Ham Unlock public void unlock() { graphcanvas.unlock(); options.unlock(); } } Đầu vào: Ta có thể vẽ mạng ngay trong phần mềm và sau đó chạy thực thi chương trình để tìm đường đi ngắn nhất trong mạng. Trong chương trình còn có ví dụ minh họa cho sẵn để giúp người sử dụng dễ hình dung được về chương trình. Các bước để vẽ một mạng được hướng dẫn cụ thể trong Documentation. Ta có thể vẽ một mạng như ví dụ đã cho ban đầu như sau. Sử dụng chuột click lên screen của ứng dụng để vẽ các đỉnh (đỉnh màu xanh là đỉnh xuất phát). Click vào một đỉnh và rê chuột đến đỉnh khác để thiết lập chi phí (khoảng cách) giữa 2 đỉnh. Click vào các mũi tên màu đen và kéo rê chuột đểt thay đổi chi phí (khoảng cách) giữa 2 đỉnh. Hoặc ta có thể chọn ví dụ cho sẵn bằng cách nhấn Button Example. Đầu ra (output): Ta có thể xem từng bước thực hiện chương trình bằng cách nhấn Button Step hoặc cho chương trình tự chạy đến khi kết thúc bằng cách nhấn Button Run. Kết quả hiển thị lên màn hình là đồ thị đường đi ngắn nhất trong mạng với đỉnh xuất phát (màu xanh dương) và các đỉnh còn lại màu xanh lá cây. Đường đi ngắn nhất qua các đỉnh sẽ được hiển thị màu xanh lá cây và trọng số từ đỉnh xuất phát đến các đỉnh kia sẽ được hiện thị ở bên trong hình trong mô tả đỉnh. Kết quả của ví dụ đã cho sẽ được minh họa như sau: Kết quả của Example được minh họa như sau: Ứng dụng đối với Open Shortest Path First (OSPF): Khái quát về Open Shortest Path First: Open Shortest Path Fisrt (OSPF) được phát triển bởi Internet Engineering Task Force (IETF) như một sự thay thế những hạn chế cũng như nhược điểm của RIP. OSPF là một link state protocol-như tên gọi của mình nó sử dụng thuật toán Dijkstra Shortest Path First (SPF) để xây dựng routing table và open nói lên tính phổ biến của nó. OSPF đã được John Moy đưa ra thông qua một số RFC, gần đây nhất là RFC 2328. Giống như các link state protocol, OSPF có ưu điểm là hội tụ nhanh, hỗ trợ được mạng có kích thước lớn và không xảy ra routing loop. Bên cạnh đó OSPF còn có những đặc trưng: +Sử dụng area để giảm yêu cầu về CPU, memory của OSPF router cũng như lưu lượng định tuyến có thể xây dựng hierarchical internetwork topologies. +Là giao thức định tuyến dạng classless nên hỗ trợ được VLSM và discontigous network. +OSPF sử dụng địa chỉ multicast 224.0.0.5 (all SPF router) 224.0.0.6 (DR và BDR router) để gửi các thông điệp Hello và Update. +OSPF còn có khả năng hỗ trợ chứng thực dạng plain text và dạng MD5. Hoạt động của OSPF (Operation of OSPF): Các OSPF-speaking router gửi các Hello packet ra tất cả các OSPF-enable interface. Nếu hai router sau khi trao đổi Hello packet và thỏa thuận một số thông số thì chúng sẽ trở thành “hàng xóm” (neightbor). Adjacency có thể được tạo qua virtual point-to-point link hay được tạo qua một vài neighbor. OSPF định nghĩa ra một số loại network và một số loại router. Sự thiết lập một adjacency được xác định bởi loại router trao đổi Hello và loại network mà Hello trao đổi qua. Mỗi router gửi các link state advertisement (LSA) qua tất cả adjacency. LSA mô tả tất cả các interface của router (link) và trạng thái của link. Các link này có thể là stub network, tới OSPF router khác, tới network trong cùng một area, tới external network. Do có rất nhiều loại link state information cho nên OSPF định nghĩa đến 11 loại LSA. Mỗi router nhận một LSA từ neighbor với link state database của neighbor đó và gửi một bản copy của LSA đến tất cả neighbor khác của nó. Bằng cách flooding các LSA toàn bộ một area, tất cả router sẽ xây dựng chính xác link state database. Khi database được hoàn tất, mỗi router sử dụng thuật toán SPF để xây dựng nên SPF tree. Mỗi router sẽ xây dựng nên routing table từ SPF tree. Tính toán SPF tree: Shortest Path First (SPF) là những tuyến đường qua mạng tới bất kì đích nào. Có hai loại đích được thừa nhận trong OSPF. Network router: Là các area border router (ABR) và autonomous system boundary router (ASBR). Chỉ một lần sau khi tất cả các OSPF router đồng bộ được link state database, mỗi router sẽ tính toán SPF tree cho mỗi đích mà nó biết. Sự tính toán này được thực hiện bởi thuật toán Dijkstra. Hình 6. Thuật toán Dijkstra biểu diễn SPF tree. Metric của OSPF: OSPF đề cập đến metric là cost. Cost của toàn tuyến là tổng của cost của các outgoing interface dọc theo tuyến đường đó. Cách tính cost được IETF đưa ra trong RFC 2328. Cisco đã thực thi cách tính cost của riêng mình như sau: 108/bandwidth với giá trị bandwidth được cấu hình cho mỗi interface.