The Difference Between Dijkstra’s Algorithm and A*

Over the last couple weeks, I’ve had an interest in brushing up my C++ skills. Friday, I came across a programming challenge that looked somewhat interesting and I thought I’d give it a shot.

The object was to find the lowest cost route between 10 cities encoded in a map of integers. Each integer represented the cost to get from that any adjacent location to that spot. This is a classic case of a graph navigation algorithm. Unfortunately, I didn’t have time to test my submission before I had to hand mine in. The deadline was Saturday so I did what I could and turned a solution in before I had to leave Saturday evening.

I ended up with the 3rd best solution for the lowest route and the 2nd best solution for time. I’m not going to discuss Dijkstra’s Algorithm here. You can view the Wikipedia definition or look it up elsewhere if you’re interested in implementing it. I’m simply going to discuss the difference between Dijkstra and A* and show what I could have done with more time to get a top score in the competition.

In Dijkstra’s algorithm you search all the verticies in the graph to determine the lowest cost route between each point. A* is a modification of Dijkstra’s algorithm that uses a heuristic to determine which vertices to search. The heuristic is the estimated cost (or distance) from the node you’re searching to the target node. The lower the heuristic, the more likely you’ll search that node’s edges next instead of some node that is further away. This leads you from the source to the target in a much faster manner. A* allows you to trade off the most accurate result for CPU time.

My route cost was quite a bit higher because I chose a heuristic that was too high. After testing a bit further, I found I could come up with a 2nd place route cost by simply lowering the heuristic a bit. This causes more nodes to be searched, and the algorithm run time to climb, but the result is more accurate. Doing away with the heuristic altogether yields a route cost of 2801, which is the same route cost that the 1st place entry received. The execution time goes up to 36 seconds in that case however. The more accurate Euclidian heuristic (linear distance) yields 2819 and costs 10 seconds.

My 2nd issue was implementation details. I think the algorithm is actually coded correctly but I used data structures that needed constructed and destroyed many times during the algorithm search. I planned on coding the algorithm correctly 1st and then optimizing it but didn’t have time to do the latter. The 1st optimization I’d make is to store node pointers instead of nodes and then only construct a node once during the algorithm’s search cycle. I don’t know if this would have yielded the fastest program or not. Either way, it’ll save a lot of cpu cycles.

Anyway, I accomplished my goal of re-familiarizing myself with lots of STL structures, some iostream details and a few C++ quirks that I hadn’t used or remembered for a while. Perhaps I’ll do better with Challenge 13.

GTK+ programs with GtkBuilder and dynamic signal handlers.

Well, I decided to review some GTK+ and Gnome development lately. With GTK+, a nice way to create a user interface is with the Glade Interface Designer. Glade produces an xml file with a glade-interface element that can be loaded by libglade. You can then change attributes of the user interface without having to recompile your program. You just edit the design xml file and you’re good to go. Here are a couple things I noted during the process that weren’t too clear from the documentation:

  1. You have to work with C, not C++, if you want to dynamically load the signal handlers. Many times, it is convenient to write a program mostly in C, but use the C++ compiler and take advantage of a few of the niceties in C++. You can’t do that in this case. According to the libglade documentation, you’ll need to add -export-dynamic flag so that the dynamic loader for the signal handlers can locate the functions in the executable with the gmodule library. That doesn’t work with a C++ compiled executable. You’ll have to stick with C. If you really want to use GTK+ with C++, you can always try the glademm bindings instead of the default C bindings. You could also use gtkmm and write the entire program w/ C++ instead.

    UPDATE: I think you could get around this by using extern “C” around the function calls for the signal handlers. Then you could still use the automatic signal handlers while compiling with g++.

  2. As of GTK+ 2.0, libglade is deprecated. There is a new GtkBuilder interface that does the same thing. You no longer need to compile and link against the libglade libraries. I searched all over for a new interface designer to replace Glade but found a lot of references to people still using Glade. The xml file produced by glade is not exactly the same and not compatible with the GtkBuilder interface however. I finally found that there is a conversion function included with GTK+ 2.0 that converts the glade file to a GtkBuilder xml file.

    gtk-builder-convert <input file> <output file>

Anyway, with those two items taken care of, here is a really simple program and a really simple Makefile I put together to show how to get a GTK+ 2.0 program window showing.

hello.c

#include 
void close_app(GtkWidget* widget,gpointer user_data) {
 gtk_main_quit();
}
int main (int argc, char **argv) {
 GtkBuilder *gtkBuilder;
 GtkWidget *mainwin;
 gtk_set_locale();
 /* Initialize the widget set */
 gtk_init (&argc, &argv);
 /* Create the main window */
 gtkBuilder= gtk_builder_new();
 gtk_builder_add_from_file(gtkBuilder,"hello.ui",NULL); 
 gtk_builder_connect_signals ( gtkBuilder, NULL );
 mainwin= GTK_WIDGET(gtk_builder_get_object(gtkBuilder,"window1"));
 g_object_unref ( G_OBJECT(gtkBuilder) );
 /* Show the application window */
 gtk_widget_show_all ( mainwin );
 /* Enter the main event loop, and wait for user interaction */
 gtk_main ();
 /* The user lost interest */
 return 0;
}

MakeFile
LIBS=$(shell pkg-config --cflags --libs gtk+-2.0)
CFLAGS=-Wall -g -export-dynamic
hello: hello.c hello.ui
    gcc -o hello hello.c $(LIBS) $(CFLAGS)
hello.ui: hello.glade
    gtk-builder-convert hello.glade hello.ui

hello.glade
For the sake of space, I’ll leave the xml contents out. Suffice it to say that there is a window, “window1”, and I set the destroy handler to “close_app”.

The Makefile converts hello.glade to hello.ui, which is loaded by the hello program at runtime to produce the UI. You can of course build a window dynamically at runtime and you can also choose to connect the signal handlers manually. It just struck me as a lot less C code to do it like this.